Cod sursa(job #671032)

Utilizator iulishorIulian Popescu iulishor Data 30 ianuarie 2012 16:47:09
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
vector< vector <int> > mat(100001),matt(100001);
vector<int> viz(100001),vizt(100001);
int n,m,ctc;
inline void df(int x)
{
	viz[x]=ctc;
	for(int i=0;i<mat[x].size();++i)
		if(!viz[mat[x][i]])
			df(mat[x][i]);
}
inline void dft(int x)
{
	vizt[x]=ctc;
	for(int i=0;i<matt[x].size();++i)
		if(!vizt[matt[x][i]])
			dft(matt[x][i]);
}
int main()
{
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");
	fin>>n>>m;
	for(;m;--m)
	{
		int x,y;
		fin>>x>>y;
		mat[x].push_back(y);
		matt[y].push_back(x);
	}
	for(int i=1;i<=n;++i)
		if(!viz[i] && !vizt[i])
		{
			++ctc;
			df(i);
			dft(i);
			for(int j=1;j<=n;++j)
				viz[j]=vizt[j]=min(viz[j],vizt[j]);
		}
	fout<<ctc<<"\n";
	for(int i=1;i<=ctc;++i)
	{
		for(int j=1;j<=n;++j)
			if(viz[j]==i)
				fout<<j<<" ";
		fout<<"\n";
	}
}