Cod sursa(job #698779)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 29 februarie 2012 15:58:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100010
using namespace std;
stack<int>S;
vector<int>sol[MAXN],g[MAXN],gt[MAXN];
int m,n,ctc[MAXN],componente;
bool viz[MAXN];
void df(int x)
{
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	if(!viz[g[x][i]]) df(g[x][i]);
	S.push(x);
}
void df2(int x)
{
	ctc[x]=componente;
	for(int i=0;i<gt[x].size();i++)
	if(!ctc[gt[x][i]]) df2(gt[x][i]);
}
int main()
{
	int i,j,x,y;
	ifstream fi("ctc.in");
	ofstream fo("ctc.out");
	fi>>n>>m;
	for(i=1;i<=m;i++)
	{
		fi>>x>>y;
		g[x].push_back(y);
		gt[y].push_back(x);
	}
	for(i=1;i<=n;i++) 
		if(!viz[i]) df(i);
	while(!S.empty())
	{
		while(!S.empty() and ctc[S.top()]) S.pop();
		if(S.empty()) break;
		x=S.top(); S.pop();
		componente++;
		df2(x);
	}
	fo<<componente<<"\n";
	for(i=1;i<=n;i++) sol[ctc[i]].push_back(i);
	for(i=1;i<=componente;i++)
	{
		for(j=0;j<sol[i].size();j++) fo<<sol[i][j]<<" ";
		fo<<"\n";
	}
	return 0;
}