Cod sursa(job #354397)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 7 octombrie 2009 21:56:34
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define nMax 100010
int n,m,nrSol;
vector <int> a[nMax];
vector <int> gt[nMax];
vector <int> ut(nMax,0);
vector <int> rez[nMax];
vector <int> noD(1);
void solve(int N)
{
	stack <int> st;
	st.push(N);
	ut[N]=1;
	vector <int> ut1(n+1,0);
	while(!st.empty())
	{
		int nod=st.top();
		st.pop();
		ut1[nod]=1;
		for(vector <int> ::iterator it=a[nod].begin();it!=a[nod].end();it++)
			if(ut[*it]==0)
			{
				st.push(*it);
				ut[*it]=1;
			}
	}
	st.push(N);
	ut[N]=2;
	while(!st.empty())
	{
		int nod=st.top();
		st.pop();
		for(vector <int> ::iterator it=gt[nod].begin();it!=gt[nod].end();it++)
			if(ut[*it]==1)
			{
				st.push(*it);
				ut[*it]=2;
			}
	}
	nrSol++;
	for(int i=1;i<=n;i++)
	{
		if(ut[i]==2)
		{
			ut[i]=3;
			rez[nrSol].push_back(i);
		}
		if(ut1[i]==1&&ut[i]==1)
				ut[i]=0;
	}
	if(rez[nrSol].empty())
		nrSol--;
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		gt[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		noD.push_back(i);
	random_shuffle(noD.begin()+1,noD.end());
	for(int i=1;i<=n;i++)
		if(!ut[noD[i]])
			solve(noD[i]);
	printf("%d\n",nrSol);
	for(int i=1;i<=nrSol;i++)
	{
		for(vector <int> ::iterator it=rez[i].begin();it!=rez[i].end();it++)
			printf("%d ",*it);
		printf("\n");
	}
	return 0;
}