Cod sursa(job #1894962)

Utilizator marcdariaDaria Marc marcdaria Data 27 februarie 2017 18:14:10
Problema Componente tare conexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <fstream>
#include <bitset>

using namespace std;

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

const int MaxN=100005;
vector<int> G[MaxN];
int d[MaxN], low[MaxN], deep, N, M;
stack<int> Stack;
bitset<MaxN> inStack;
set<set<int>> SCC;

void Read();
void Tarjan(int x);

int main()
{
	Read();
	for(int i=1;i<=N;++i)
	   if(!d[i])
	   Tarjan(i);

	fout<<SCC.size()<<'\n';

	for(set<set<int>>::iterator it=SCC.begin();it!=SCC.end();++it, fout<<'\n')
	   for(set<int>::iterator itt=it->begin();itt!=it->end();++itt)
	      fout<<*itt<<' ';

	fout.close();
	return 0;
}

void Read()
{
	fin>>N>>M;
	while(M--)
	{
		int x,y;
		fin>>x>>y;
		G[x].push_back(y);
	}
	fin.close();
}
void Tarjan(int x)
{
	d[x]=low[x]=deep++;
	Stack.push(x);
	inStack[x]=true;

	for(auto y : G[x])
	{if(!d[y])
	{
		Tarjan(y);
		low[x]=min(low[x],low[y]);
	}
	if(inStack[y])
	low[x]=min(low[x],low[y]);
	}
	if(low[x]==d[x])
	{
		set<int> actualSCC;
		int node;
		while(node!=x)
		{
			actualSCC.insert(node=Stack.top());
			Stack.pop();
			inStack[node]=false;
		}
		SCC.insert(actualSCC);
	}
}