Cod sursa(job #1221214)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 19 august 2014 21:34:21
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <stack>
#include <vector>
#include <utility>

using namespace std;

#define MAX  140000

int to_print[MAX], idx, cnt;
int n, m;
vector<pair<bool, vector<int>>> adj[2];	// 0 - graf normal, 1 graf intors
stack<int> s;

void dfs(int which, int nod){
	adj[which][nod].first = true;
	for(int i = 0; i < adj[which][nod].second.size(); i++){
		if(!adj[which][adj[which][nod].second.at(i)].first){
			if(which)
				to_print[idx++] = adj[which][nod].second.at(i) + 1;
			dfs(which, adj[which][nod].second.at(i));
		}
	}
	if(!which)
		s.push(nod);
}

int main(){
	int a, b;
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	cin >> n >> m;

	vector<int> v;
	for(int i = 0; i < n; i++){
		adj[0].push_back(make_pair(false, v));
		adj[1].push_back(make_pair(false, v));
	}

	for(int i = 0; i < m; i++){
		cin >> a >> b;
		adj[0][--a].second.push_back(--b);
		adj[1][b].second.push_back(a);
	}

	for(int i = 0; i < n; i++){
		if(!adj[0][i].first){
			dfs(0, i);
		}
	}

	while(!s.empty()){
		int nod = s.top();
		s.pop();
		if(!adj[1][nod].first){
			dfs(1, nod);
			to_print[idx++] = nod+1;
			idx++;
			cnt++;
		}
	}
	cout << cnt << "\n";
	for(int i = 0; i < idx; i++){
		if(!to_print[i])
			cout << "\n";
		else
			cout << to_print[i] << " ";
	}
	return 0;
}