Cod sursa(job #1182568)

Utilizator xoSauceSergiu Ferentz xoSauce Data 6 mai 2014 20:22:50
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

int n,m;
vector<int> v1[100500];
vector<int> v2[100500];
bool markA[100500];
stack<int> finish;
vector< stack<int> > solution;

void dfsA(int node){
	markA[node] = true;
	for(int i = 0; i < v1[node].size(); i++){
		if(!markA[v1[node][i]])
			dfsA(v1[node][i]);
	}
	finish.push(node);
}

void dfsB(int node,int &cnt){
	markA[node] = true;
	solution[cnt].push(node);
	for(int i =0 ; i < v2[node].size(); i++){
		if(!markA[v2[node][i]])
			dfsB(v2[node][i],cnt);
	}
}
int main(){

	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 0; i < m; i++){
		int x,y;
		scanf("%d %d",&x,&y);
		v1[x].push_back(y);
		v2[y].push_back(x);
	}

	for(int i =1 ; i <= n; i++){
		if(!markA[i])
			dfsA(i);
	}
	memset(markA,0,sizeof markA);
	int cnt =0;
	while(!finish.empty()){
		if(markA[finish.top()]){
			finish.pop();
			continue;
		}
		dfsB(finish.top(),cnt);
		finish.pop();
		cnt++;
	}
	cout << cnt << endl;
	for(int i =0 ; i < cnt; i++){
		while(!solution[i].empty()){
			cout << solution[i].top() << " ";
			solution[i].pop();
		}
		cout << endl;
	}

}