Cod sursa(job #592385)

Utilizator ms-ninjacristescu liviu ms-ninja Data 28 mai 2011 10:58:47
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define dim 200001
vector <int> v[dim];
vector <int> mat[dim];
vector <int> sol[dim];
//vector <int> lol[dim];
int viz[dim],conex,coada[dim],inc;
bool viz2[dim];


void dfs(int nod)
{
	viz[nod]=conex;
	coada[++inc]=nod;
	for(int i=0;i<v[nod].size();++i)
		if(viz[v[nod][i]]==0)
			dfs(v[nod][i]);
}

void dfs1(int nod)
{
	viz2[nod]=1;
	for(int i=0;i<mat[nod].size();++i)
		if(viz2[mat[nod][i]]==0)
			dfs1(mat[nod][i]);
}

int main()
{
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");
	int n, m, a, b, i, j;
	
	fin>>n >>m;
	for(i=1;i<=m;++i)
	{
		fin>>a>>b;
		v[a].push_back(b);
		mat[b].push_back(a);
	}

	for(i=1;i<=n;++i)
		if(viz[i]==0)
		{
			inc=0;
			++conex;
			dfs(i);
			dfs1(i);
			
			for(j=1;j<=inc;++j)
			{
				if(viz[coada[j]]==conex)
					if(viz2[coada[j]]==0)
						viz[coada[j]]=0;
					else
						sol[conex].push_back(coada[j]);
				//viz2[coada[j]]=0;
			}
			
			for(int k=1;k<=n;++k)
				viz2[k]=0;
		}
	
	fout<<conex<<'\n';
	
	for(i=1;i<=conex;++i)
	{
		for(j=0;j<sol[i].size();++j)
			fout<<sol[i][j]<<" ";
		fout<<'\n';
	}	
		
	return 0;
}