Cod sursa(job #631997)

Utilizator sergiupPopescu Sergiu sergiup Data 10 noiembrie 2011 00:00:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

#define MAXN 100005
int n,m;

vector<int> g[MAXN];
vector<int> gt[MAXN];
bool viz[MAXN];
bool vizt[MAXN];
stack<int> st;
vector<int> sol[MAXN];

int cindex = 0;

void dfs(int nod) {
	viz[nod] = 1;
	for (int i = 0 ; i < g[nod].size() ; ++i) {
		if (!viz[g[nod][i]]) {
			dfs(g[nod][i]);
		}
	}
	st.push(nod);
}

void dfst(int nod) {
	vizt[nod] = 1;
	for (int i = 0 ; i < gt[nod].size() ; ++i) {
		if (!vizt[gt[nod][i]]) {
			dfst(gt[nod][i]);
		}
	}
	sol[cindex].push_back(nod);
}

int main() {
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d %d",&n,&m);

	int x,y;
	for (int i = 0 ; i < m ; ++i) {
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		gt[y].push_back(x);
	}

	for (int i = 1 ; i <= n ; ++i) {
		if (!viz[i]) {
			dfs(i);
		}
	}

	while (!st.empty()) {
		if (!vizt[st.top()]) {
			dfst(st.top());
			cindex++;
		}
		st.pop();
	}
	
	printf("%d\n",cindex);

	for (int i = 0 ; i < cindex ; ++i) {
		for (int j = 0 ; j < sol[i].size() ; ++j) {
			printf("%d ",sol[i][j]);
		}
		printf("\n");
	}

	return 0;
}