Cod sursa(job #786460)

Utilizator xulescuStefu Gabriel xulescu Data 11 septembrie 2012 14:11:35
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

#define min(a, b) ((a)<(b)?(a):(b))

long n, m;

struct edge{
	long to;
	edge *next;
};

struct node{
	long index, lowlink;
	bool inStack;
	edge *neigh;
	node() : index(-1), lowlink(-1), inStack(false), neigh(NULL){}
};

node graf[100001];

void inline add_edge(long from, long to){
	edge *e = new edge;
	e->to = to;
	e->next = graf[from].neigh;
	graf[from].neigh = e;
}

stack<long> S;
vector<vector<long> > sol;

long index = 0;

void proc(long nod){
	node& cur = graf[nod];
	cur.index = index;
	cur.lowlink = index;
	index++;
	S.push(nod);
	cur.inStack = true;

	edge *p = cur.neigh;
	while(p){
		node& w = graf[p->to];
		if(w.index == -1){
			// not yet visited
			proc(p->to);
			cur.lowlink = min(cur.lowlink, w.lowlink);
		}
		else if(graf[p->to].inStack){
			cur.lowlink = min(cur.lowlink, w.index);
		}
		p = p->next;
	}

	if(cur.index == cur.lowlink){
		vector<long> comp;
		while(S.top() != nod){
			long w = S.top();
			S.pop();
			graf[w].inStack = false;
			comp.push_back(w);
		}
		S.pop();
		cur.inStack = false;
		comp.push_back(nod);

		sol.push_back(comp);
	}
}

int main(){
	ifstream f("ctc.in");
	f >> n >> m;
	long u, v;
	for(int i=0; i<m; i++){
		f >> u >> v;
		add_edge(u, v);
	}
	f.close();

	for(int i=1; i<=n; i++){
		if(graf[i].index == -1){
			proc(i);
		}
	}

	ofstream g("ctc.out");
	g << sol.size() << endl;
	for(vector<vector<long> >::iterator it = sol.begin(); it != sol.end(); it++){
		for(vector<long>::iterator it1 = it->begin(); it1 != it->end(); it1++){
			g << *it1 << " ";
		}
		g << endl;
	}
	g.close();

	return 0;
}