Cod sursa(job #1494152)

Utilizator deividFlorentin Dumitru deivid Data 30 septembrie 2015 19:16:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>
#include <stack>
#include <vector>

#define maxdim 100005

using namespace std;

int n, m;
int viz[maxdim];
vector<int> G[maxdim], Gt[maxdim];
stack<int> st;
vector<vector<int>> sol;

void dfs1(int nod) {
	viz[nod] = 1;
	
	for (int vecin : G[nod]) {
		if (!viz[vecin]) {
			dfs1(vecin);
		}
	}
	st.push(nod);
}

void dfs2(int nod, vector<int> &crt) {
	viz[nod] = 0;
	
	crt.push_back(nod);
	for (int vecin : Gt[nod]) {
		if (viz[vecin]) {
			dfs2(vecin, crt);
		}
	}
}

int main() {
	
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int x, y; 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]) {
			dfs1(i);
		}
	}
	
	while (!st.empty()) {
		int nod = st.top(); st.pop();
		if (viz[nod]) {
			vector<int> crt;
			dfs2(nod, crt);
			sol.push_back(crt);
		}
	}
	
	printf("%d\n", (int) sol.size());
	for (vector<int> &crt : sol) {
		for (int nod : crt) {
			printf("%d ", nod);
		}
		printf("\n");
	}

	return 0;
}