Cod sursa(job #456311)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 15 mai 2010 09:14:42
Problema Party Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define oo 1<<30
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((int)(V.size()))
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define FOR(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (int (i)=0;(i)<(int)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)

#define IN  "party.in"
#define OUT "party.out"
#define N_MAX (1<<8)
#define non(x) ( (x) <= N ? (x) + N : (x) - N )

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;
template<class T> string toString(T n) {ostringstream ost;ost<<n;ost.flush();return ost.str();}

int N,M,S[N_MAX];
vector<VI> A(N_MAX),B(N_MAX);
bitset<N_MAX> viz,Sol;
bool Aedge[N_MAX][N_MAX],Bedge[N_MAX][N_MAX];

II void add_edge(int x,int y)
{
	if(!Aedge[x][y])
	{
		A[x].pb(y);
		Aedge[x][y] = true;
	}
	if(!Bedge[y][x])
	{
		B[y].pb(x);
		Bedge[y][x] = true;
	}
}

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	
	scanf("%d%d",&N,&M);
	int x,y,z;
	FOR(i,1,M)
	{
		scanf("%d%d%d",&x,&y,&z);
		switch(z)
		{
			case 0: { add_edge( non(x),y); add_edge( non(y),x ); break;};
			case 1: { add_edge( non(x),non(y) ); add_edge( y,x ); break;};
			case 2: { add_edge( non(y),non(x) ); add_edge( x,y ); break;};
			case 3:	{ add_edge( x,non(y) ); add_edge( y,non(x) ); break;};
		}
	}
}

II void DFP(int nod)
{
	viz[nod] = true;
	
	FORit(it,A[nod])
		if(!viz[*it])
			DFP(*it);
	S[++S[0]] = nod;
}

II void DFM(int nod)
{
	viz[nod] = true;
	Sol[ non(nod) ] = true;
	
	FORit(it,B[nod])
		if(!viz[*it])
			DFM(*it);
}

II void solve()
{
	FOR(i,1,N + N)
		if(!viz[i])
			DFP(i);
	
	viz.reset();
	
	for(int i = N + N;i >= 1;--i)
		if( !viz[ S[i] ] && !viz[ non(S[i]) ] )
			DFM(S[i]);
	
	S[0] = 0;
	FOR(i,1,N)
		if(Sol[i] == true)
			S[++S[0]] = i;
	
	printf("%d\n",S[0]);
	FOR(i,1,S[0])
		printf("%d\n",S[i]);
}

int main()
{
	scan();
	solve();
	return 0;
}