Cod sursa(job #990217)

Utilizator helios11radu mihai helios11 Data 27 august 2013 18:09:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <stdio.h>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;

int N, M;
vector<int> adjacence_list[100011];
int index[100011];
int backlink[100011];
int ind = 0;
stack<int> S;
vector<set<int>> result;

int nr = 0;

void read(){
	int from, to;
	
	scanf("%d %d", &N, &M);
	for(int i = 1; i <= N; ++i){
		index[i] = -1;
	}
	for(int i = 0; i < M; ++i){
		scanf("%d %d", &from, &to);
		adjacence_list[from].push_back(to);
	}
	/*
	for(int i = 1; i <= N; ++i){
		vector<int>::iterator it;
		printf("%d ", i);
		for(it = adjacence_list[i].begin(); it != adjacence_list[i].end(); ++it){
			printf("%d ", *it);
		}
	}*/
}

void tarjan(int node){
	
	index[node] = ind;
	backlink[node] = ind;
	++ind;
	S.push(node);

	//go through neighbours
	vector<int>::iterator it;
	for(it = adjacence_list[node].begin(); it!= adjacence_list[node].end(); ++it){
		if(index[(*it)] == -1){ // if it hasn't been visited yet
			tarjan(*it);
			backlink[node] = min(backlink[*it], backlink[node]);
		}
		else if(index[(*it)] != -2){ // if *it is in the stack (-2 means that node has taen part in a scc that was already discovered and discarded)
			backlink[node] = min(backlink[node], backlink[*it]);
		}
	}

	//see if node is a root of scc
	if(backlink[node] == index[node]){
		//printf("intra\n");
		++nr;
		set<int> s;
		result.push_back(s);
		int popped;
		do{
			popped = S.top();
			index[popped] = -2;
			S.pop();
			result.back().insert(popped);
		} while(popped != node);
	}

}
int main(){
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	read();
	
	for(int i = 1; i <= N; ++i){
		if(index[i] == -1){// not visited
			tarjan(i);
		}
	}
	
	printf("%d\n", nr);
	vector<set<int>>::iterator it;
	
	for(it = result.begin(); it != result.end(); ++it){
		set<int>::iterator it1;
		for(it1 = (*it).begin(); it1 != (*it).end(); ++it1){
			printf("%d ", (*it1));
		}
		printf("\n");
	}
	return 0;
}