Cod sursa(job #354398)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 7 octombrie 2009 21:59:52
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 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);
	vector <int> utFirst(ut);
	utFirst[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(utFirst[*it])
				continue;
			st.push(*it);
			utFirst[*it]=1;
		}
	}
	st.push(N);
	vector <int> utSecond(ut);
	utSecond[N]=1;
	vector <int> ut2(n+1,0);
	while(!st.empty())
	{
		int nod=st.top();
		st.pop();
		ut2[nod]=1;
		for(vector <int> ::iterator it=gt[nod].begin();it!=gt[nod].end();it++)
		{
			if(utSecond[*it])
				continue;
			st.push(*it);
			utSecond[*it]=1;
		}
	}
	nrSol++;
	for(int i=1;i<=n;i++)
		if(ut1[i]&&ut2[i])
		{
			ut[i]=1;
			rez[nrSol].push_back(i);
		}
	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;
}