Cod sursa(job #715265)

Utilizator lucian666Vasilut Lucian lucian666 Data 16 martie 2012 22:22:24
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
#define NN 100001
using namespace std;
ofstream out("ctc.out");
vector<vector<int> >G;
vector<vector<int> >G1;
int v1[NN],v2[NN],n,m,rez;
void citire();
void dfs1(int,int);
void dfs2(int,int);
int main()
{
	citire();
	for(int i=1;i<=n;i++)
	if(!v1[i]&&!v2[i])
	{
		++rez;
		dfs1(i,rez);
		dfs2(i,rez);
		for(int j=1;j<=n;j++)
			v1[j]=v2[j]=min(v1[j],v2[j]);
	}
	out<<rez<<'\n';
	for(int j=1;j<=rez;j++)
	{
		for(int i=1;i<=n;i++)
			if(v1[i]==j)
				out<<i<<" ";
			out<<'\n';
	}
return 0;
}

void dfs1(int x,int cul)
{
	v1[x]=cul;
	for(vector<int>::iterator i=G[x].begin();i<G[x].end();++i)
		if(!v1[*i])
			dfs1(*i,cul);
}
void dfs2(int x,int cul)
{
	v2[x]=cul;
		for(vector<int>::iterator i=G1[x].begin();i<G1[x].end();++i)
			if(!v2[*i])
				dfs2(*i,cul);
}
void citire()
{
	ifstream in("ctc.in");
		in>>n>>m;
		G.resize(n+1);
		G1.resize(n+1);
		for(int x,y;m;--m)
		{
			in>>x>>y;
			G[x].pb(y);
			G1[y].pb(x);
		}
}