Cod sursa(job #663554)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 18 ianuarie 2012 18:09:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<vector>
#define NMAX 100100
using namespace std;
vector <int> G[NMAX],Gt[NMAX],sol[NMAX];
int n,nr,comp,deque[NMAX],viz[NMAX];

void dfs(int nod) {
	int i;
	viz[nod]=0;
	sol[comp].push_back(nod);
	for(i=0;i<Gt[nod].size();i++)
		if(viz[Gt[nod][i]])
			dfs(Gt[nod][i]);
}
void sort_top(int nod) {
	int i;
	viz[nod]=1;
	for(i=0;i<G[nod].size();i++)
		if(!viz[G[nod][i]])
			sort_top(G[nod][i]);
	deque[nr--]=nod;
}
void citire() {
	int i,x,y,m;
	ifstream in("ctc.in");
	in>>n>>m;
	for(i=0;i<m;i++) {
		in>>x>>y;
		G[x].push_back(y);
		Gt[y].push_back(x);
		}
	in.close();
}
void afis() {
	int i,j;
	ofstream out("ctc.out");
	out<<comp<<'\n';
	for(i=0;i<comp;i++) {
		for(j=0;j<sol[i].size();j++)
			out<<sol[i][j]<<" ";
		out<<'\n';
		}
	out.close();
}
int main() {
	int i;
	citire();
	nr=n;
	for(i=1;i<=n;i++)
		if(!viz[i])
			sort_top(i);
	for(i=1;i<=n;i++)
		if(viz[deque[i]]) {
			dfs(deque[i]);
			comp++;
			}
	afis();
	return 0;
}