Cod sursa(job #1373732)

Utilizator abel1090Abel Putovits abel1090 Data 4 martie 2015 20:19:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
///TARJAN
#include <iostream> 
#include <fstream>
#include <vector>
#include <stack>
#include <limits>
#include <list>

using namespace std; 

const int INF = numeric_limits<int>::max();

list<list<int> > answ;;

struct Node {
	int ind, low;
	bool inQ;

	Node() {
		ind = low = INF;
		inQ = false;
	}
};

void findComp(vector<vector<int> >& adjList, vector<Node>& nds, 
		stack<int>& s, int v, int& ind) {
	nds[v].ind = ind;
	nds[v].low = ind;
	nds[v].inQ = true;	
	s.push(v);
	++ind;

	int w;
	for(int i=0; i<adjList[v].size(); ++i) {
		w = adjList[v][i];
		if(nds[w].ind == INF) {
			findComp(adjList, nds, s, w, ind);
			nds[v].low = min(nds[v].low, nds[w].low);
		} else
			if(nds[w].inQ)
				nds[v].low = min(nds[v].low, nds[w].ind);
	}	

	///if v is a root of a strongly connected component
	if(nds[v].low == nds[v].ind) {
		list<int> comp;
		do {			
			w = s.top();
			s.pop();
			nds[w].inQ = false;
			comp.push_back(w);
		} while(v != w);
		answ.push_back(comp);
	}
}

int main() {
	ifstream inStr("ctc.in");
	ofstream outStr("ctc.out");
	
	int N, M;
	inStr >> N >> M;

	vector<vector<int> > adjList(N);
	
	int fr, to;
	for(int i=0; i<M; ++i) {
		inStr >> fr >> to;
		adjList[--fr].push_back(--to);
	}

	vector<Node> nds(N, Node()); 
	stack<int> s;
	int ind = 0;

	for(int i=0; i<N; ++i)
		if(nds[i].ind == INF) 
			findComp(adjList, nds, s, i, ind);

	outStr << answ.size() << '\n';
	
	for(list<list<int> >::iterator i=answ.begin(); i!=answ.end(); ++i) {
		for(list<int>::iterator j=i->begin(); j!=i->end(); ++j)
			outStr << *j+1 << ' ';
		outStr << '\n';
	}
			
	return 0;
}