Cod sursa(job #1244940)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 octombrie 2014 14:00:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <stack>
#include <vector>

#define MAX  100001

using namespace std;

int N, M;
stack<int> st;
vector<vector<int>> adj(MAX);
vector<vector<int>> adjRev(MAX);
vector<bool> marked(MAX, false);
vector<vector<int>> answer;
vector<int> ans;

void dfs(int source){
	for(int i = 0; i < adj[source].size(); i++){
		if(!marked[adj[source][i]]){
			marked[adj[source][i]] = true;
			dfs(adj[source][i]);
		}
	}
	st.push(source);
}

void dfsRev(int source){
	for(int i = 0; i < adjRev[source].size(); i++){
		if(!marked[adjRev[source][i]]){
			marked[adjRev[source][i]] = true;
			dfsRev(adjRev[source][i]);
		}
	}
	ans.push_back(source);
}

int main(){
	int from, to;
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++){
		scanf("%d%d", &from, &to);
		adj[--from].push_back(--to);
		adjRev[to].push_back(from);
	}
	
	dfs(0);
	
	marked.assign(MAX, false);
	
	while(!st.empty()){
		if(!marked[from = st.top()]){
			ans.clear();
			marked[from] = true;
			dfsRev(from);
			answer.push_back(ans);		
		}
		st.pop();
	}

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