OJ Board

Code: Select all

2

10
3 2 3 4
1 6
0
1 5
0
1 9
3 8 9 10
0
1 3
0

20
3 2 3 4
0
0
0

Code: Select all

0
19

Code: Select all

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <string>
#include <strstream>
using namespace std;

#define MAXN	220
typedef struct {
	int NrFriend, NrEnermy, illegal;
} Group;

int bipartite[MAXN][2];
int depth[MAXN];
Group g[MAXN];
int N;

int set_enermy(int x, int y)
{
	int a,b,r1,r2;

	for (a = x, r1 = 0; bipartite[a][0] != -1; r1 += bipartite[a][1], a = bipartite[a][0]);
	for(b = y, r2 = 0; bipartite[b][0] != -1; r2 += bipartite[b][1], b = bipartite[b][0]);

	if (a==b && (r1+r2)%2 != 1) {
		g[a].illegal = 1;
		return 0;
	}

	if (a != b) {
		if (depth[a] < depth[b]) {
			bipartite[a][0] = b;
			bipartite[a][1] = (r1+r2+1)%2;
			if (bipartite[a][1] % 2 == bipartite[b][1] % 2) {
				g[b].NrEnermy += g[a].NrEnermy;
				g[b].NrFriend += g[a].NrFriend;
			} else {
				g[b].NrEnermy += g[a].NrFriend;
				g[b].NrFriend += g[a].NrEnermy;
			}
		} else {
			bipartite[b][0] = a;
			bipartite[b][1] = (r1+r2+1)%2;
			if (bipartite[a][1] % 2 == bipartite[b][1] % 2) {
				g[a].NrEnermy += g[b].NrEnermy;
				g[a].NrFriend += g[b].NrFriend;
			} else {
				g[a].NrEnermy += g[b].NrFriend;
				g[a].NrFriend += g[b].NrEnermy;
			}
			if (depth[a] == depth[b]) {
				depth[a]++;
			}
		}
	}

	return 0;
}

int main()
{
	int i,j,k,testcase,maxinvitation;
	char buffer[200];

	do {
		cin.getline(buffer,200);
	} while (buffer[0] == '\n' || buffer[0] == '\0');
	istrstream strin(buffer);
	strin >> testcase;
	while (testcase--) {
		do {
			cin.getline(buffer,200);
		} while (buffer[0] == '\n' || buffer[0] == '\0');
		istrstream strin1(buffer);
		strin1 >> N;

		for (i = 1; i <= 200; i++) {
			bipartite[i][0] = -1;
			bipartite[i][1] = 0;
			depth[i] = 0;
			g[i].NrEnermy = 0;
			g[i].NrFriend = 1;
			g[i].illegal = 0;
		}

		i = 1;
		do {
			cin.getline(buffer, 200);
			if (buffer[0] == '\n' || buffer[0] == '\0') break;
			
			istrstream strin2(buffer);
			strin2 >> k;

			while (k-- > 0 && !strin2.eof()) {
				j = -1;
				strin2 >> j;
				if (i <= N && j != -1 && j <= N) {
					set_enermy(i,j);
				}
			}
		} while (i++);
		
		// printout
		maxinvitation = 0;
		for (i = 1; i<= N; i++) {
			if (bipartite[i][0] == -1 && g[i].illegal == 0) {
				maxinvitation += (g[i].NrEnermy > g[i].NrFriend)? g[i].NrEnermy : g[i].NrFriend;
			}
		}
		cout << maxinvitation << endl;
	}
	return 0;
}

Code: Select all

   char buffer[200];  

Code: Select all

	for (a = x, r1 = 0; bipartite[a][0] != -1; r1 +=bipartite[a][1], a = bipartite[a][0]);
	for (b = y, r2 = 0; bipartite[b][0] != -1; r2 +=bipartite[b][1], b = bipartite[b][0]);

Code: Select all

char buffer[1000];

Code: Select all

1

100
2 23
0
0
3 3 8 11
3 8 11 13
1 11
1 13
2 4 5
2 18 13
3 20 18 21
3 4 5 6 
1 21
0
0
0
0
1 21
2 9 10
1 21
0
4 12 17 19 25
0
0
2 25 27
4 21 22 23 24
0
2 24 26
0
3 30 37 38
3 26 28 29
0
0
0
0
0
0
1 29
2 29 31
1 40
3 31 39 51
0
0
0
0
0
0
0
0
0
0
0
0
2 58 59
0
0
1 79
2 51 52
2 53 52
1 53
0
0
0
0
0
0
0
0
0
0
0
1 53
0
1 79
0
1 53
0
0
0
1 53 54 55 56 70 72 73
0
0
0
0
3 73 74 76
0
3 76 77 83
2 90 100
1 83
0
3 83 85 87
0
0
0
0
0
0
0
0
0
2 87 89

Code: Select all

73

Code: Select all

#include<stdio.h>
long n,sa[209][209],x[209],y[209],z[209],si[209];
void make(long h1,long h2)
{
	long X,Y,i;
X=0;
Y=0;

for(i=1;i<=n;i++)
{if(sa[h2][i]==1&&si[i]==1)
X=1;
else if(sa[h2][i]==1&&si[i]==2)
Y=1;}
if(X==1&&Y==1)
{z[h1]=1;si[h2]=1;}
else if(X==1)
{y[h1]++;si[h2]=2;}
else
{x[h1]++;si[h2]=1;}

for(i=1;i<=n;i++)
if(sa[h2][i]==1&&si[i]==0)
make(h1,i);

}

void main()
{

long cas,cas1,m,i,j,sum,a,b;

scanf("%ld",&cas);

for(cas1=1;cas1<=cas;cas1++)
{

scanf("%ld",&n);

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sa[i][j]=0;

for(i=1;i<=n;i++)
si[i]=0;

for(i=1;i<=n;i++)
{
scanf("%ld",&a);
for(j=0;j<a;j++)
{
scanf("%ld",&b);
if(b<=n)
{
sa[i][b]=1;
sa[b][i]=1;
}
}
}

m=0;
for(i=1;i<=n;i++)
if(si[i]==0)
{
x[m]=1;
y[m]=0;
z[m]=0;
si[i]=1;
for(j=1;j<=n;j++)
if(sa[i][j]==1&&si[j]==0)
make(m,j);
m++;
}

for(i=0;i<m;i++)
if(y[i]>x[i])
x[i]=y[i];
sum=0;

for(i=0;i<m;i++)
if(z[i]==0)
sum+=x[i];

printf("%ld\n",sum);

}
}

Code: Select all

#include <cstdio>
#include <vector>

using namespace std;

const int MX = 300;

bool v[MX];
vector <int> gr[MX];
int kolor[MX];

int n,m,a,b,c,wynik;

void clear()
{
    for(int i=0;i<MX;i++)
    {
        v[i] = false;
        gr[i].clear();
        kolor[i] = 3;
    }
    wynik = 0;
}

int bfs(int x)
{
    vector <int> kolejka;
    kolejka.push_back(x);
    v[x] = true;
    kolor[x] = 1;
    int red = 0;
    int blue = 0;
    int next;
    bool ok = false;

    while(!kolejka.empty())
    {
        int u = kolejka.back();
        kolejka.pop_back();
        if(kolor[u]) ++red;
        else ++blue;
        next = (kolor[u]+1)&1;
        //printf("%d ",u);
        for(int j=0;j<gr[u].size();j++)
        {
            if(!v[gr[u][j]])
            {
                v[gr[u][j]] = true;
                kolor [ gr[u][j] ] = next;
                kolejka.push_back(gr[u][j]);
            }
            else
            if (kolor[u] == kolor[gr[u][j]])
                ok = true;
        }

    }
    if(ok) return 0;
    return max(red,blue);

}

int main()
{
    scanf("%d",&m);
    while(m--)
    {
        clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            while(a--)
            {
                scanf("%d",&b);
                gr[b].push_back(i);
                gr[i].push_back(b);
            }
        }
/*
        pisz();
*/
        for(int i=1;i<=n;i++)
            if(!v[i])
                wynik+=bfs(i);

        printf("%d\n",wynik);
        //if(m)puts("");
//       for(int i=1;i<=n;i++)
  //        printf("%d ",kolor[i]);
    //    puts("");

    }
}

Code: Select all

AC

Code: Select all

1

5
5 2 4 6 8 10
3 1 3 6
0
0
3 1 6 7

Code: Select all

3