Cod sursa(job #1737784)

Utilizator Bulgaru_Robert_Razvan_323CBBulgaru Robert Razvan Bulgaru_Robert_Razvan_323CB Data 4 august 2016 19:57:21
Problema Componente tare conexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

unsigned int n,m,x,y,node,indx,nrComp=0;

int idx[100005];
int lowLink[100005];
int inStack[100005];

vector<int> graph[100005];
vector<int> ctc[80000];
stack<int> st;

unsigned int min(unsigned int a,unsigned int b) {
	if (a>=b)
		return b;
	return a;
}

void tarjan(unsigned int v) {
	idx[v]=indx;
	lowLink[v]=indx;
	indx++;

	st.push(v);
	inStack[v]=1;

	for (unsigned int u=0;u<graph[v].size();u++) {
		if (idx[graph[v][u]]==-1) {
			tarjan(graph[v][u]);
			lowLink[v]=min(lowLink[v],lowLink[graph[v][u]]);
		}
		else if (inStack[graph[v][u]])
			lowLink[v]=min(lowLink[v],idx[graph[v][u]]);
	}

	if (idx[v]==lowLink[v]) {
		nrComp++;

		do {
			node=st.top();
			st.pop();
			inStack[node]=0;
			ctc[nrComp].push_back(node);
		}while (node!=v);
	}
}

void ctcTarjan() {
	indx=0;

	for (unsigned int i=1;i<=n;i++) 
		if (idx[i]==-1)
			tarjan(i);
}

int main() {
	memset(idx,-1,sizeof(idx));
	memset(lowLink,0,sizeof(lowLink));
	memset(inStack,0,sizeof(inStack));

	in>>n>>m;

	for (unsigned int i=0;i<m;i++) {
		in>>x>>y;
		graph[x].push_back(y);
	}

	ctcTarjan();

	out<<nrComp<<"\n";

	for (unsigned int i=1;i<=nrComp;i++) {
		for (unsigned int j=0;j<ctc[i].size();j++) {
			out<<ctc[i][j]<<" ";
		}
		out<<"\n";
	}
	return 0;
}