Cod sursa(job #744376)

Utilizator lucian666Vasilut Lucian lucian666 Data 8 mai 2012 15:47:13
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define NN 100001
#define pb push_back
using namespace std;
ofstream out("ctc.out");
vector<int>G[NN];
vector<int>G1[NN];
int v1[NN],v2[NN],n,m;
void DFS(vector<int>*g,int ,int ,int *),citire();
int main()
{
	citire();
	int rez=0;
	for(int i=1;i<=n;i++)
		if(!v1[i]&&!v2[i])
		{
			++rez;
			DFS(G,i,rez,v1);
			DFS(G1,i,rez,v2);
			for(int j=1;j<=n;j++)
				v1[j]=v2[j]=min(v1[j],v2[j]);
		}
		out<<rez<<'\n';
		for(int i=1;i<=rez;++i)
		{
			for(int j=1;j<=n;++j)
				if(v1[j]==i)
					out<<j<<" ";
				out<<'\n';
		}
		return 0;
}
void citire()
{
	ifstream in("ctc.in");
	in>>n>>m;
	for(int i,j;m;--m)
	{
		in>>i>>j;
		G[i].pb(j);
		G1[j].pb(i);
	}
}
void DFS(vector<int>*g,int start ,int cul ,int v[100])
{
	v[start]=cul;
		for(vector<int>::iterator i=g[start].begin();i<g[start].end();++i)
			if(!v[*i])
				DFS(g,*i,cul,v);
}