Cod sursa(job #2230807)

Utilizator rrobertBulgaru Robert rrobert Data 11 august 2018 16:18:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

#define UNDEF -1

int x,y,index,N,M;
int low[100005],idx[100005];
bool in_stack[100005];
stack<int> st;
vector<int> g[100005];
vector<vector<int> > result;

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

int min(int a,int b) {
	return a<b?a:b;
}

void tarjan(int v) {
	idx[v]=index;
	low[v]=index;
	index=index+1;
	st.push(v);
	in_stack[v]=true;

	for (int u=0;u<g[v].size();u++) {
		if (idx[g[v][u]]==UNDEF) {
			tarjan(g[v][u]);
			low[v]=min(low[v],low[g[v][u]]);
		}
		else if (in_stack[g[v][u]])
			low[v]=min(low[v],idx[g[v][u]]);
	}

	if (idx[v]==low[v]) {
		result.push_back(vector<int>());
		int node;
		do {
			node=st.top();
			st.pop();
			in_stack[node]=false;
			result[result.size()-1].push_back(node);
		}while (v!=node);
	}
}

void ctc() {
	index=0;
	for (int i=1;i<=N;i++)
		if (idx[i]==UNDEF)
			tarjan(i);
}

int main() {
	in>>N>>M;
	for (int i=1;i<=M;i++) {
		in>>x>>y;
		in_stack[x]=false; idx[x]=UNDEF; low[x]=0;
		in_stack[y]=false; idx[y]=UNDEF; low[y]=0;
		g[x].push_back(y);
	}

	ctc();

	out<<result.size()<<"\n";
	for (int i=result.size()-1;i>=0;i--) {
		for (int j=result[i].size()-1;j>=0;j--)
			out<<result[i][j]<<" ";
		out<<"\n";
	}

	in.close();
	out.close();
	return 0;
}