Cod sursa(job #1735466)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 29 iulie 2016 23:17:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> idx;
vector<int> lowlink;
vector<vector<int> > graph;
vector<vector<int> > ctc;
int nrCtc = 0;
vector<bool> in_stack;
stack<int> s;
int index = 0;
int n,m;
void tarjan (int v)
{
	idx[v] = index;
	lowlink[v] = index;
	index = index+1;
	s.push(v);
	in_stack[v] = true;
	for (int i = 0; i < graph[v].size(); i++)
	{
		if (idx[graph[v][i]] == -1)
		{
			tarjan(graph[v][i]);
			lowlink[v] = min (lowlink[v], lowlink[graph[v][i]]);
		}
		else
		{
			//nu iau in cosiderare arcele transversale
			if (in_stack[graph[v][i]] == true)
			{
				lowlink[v] = min (lowlink[v], lowlink[graph[v][i]]);
			}
		}
	}
	if (lowlink[v] == idx[v])
	{
		nrCtc++;
		ctc.resize(ctc.size()+1);
		int u = s.top();
		s.pop();
		//cout<<u<<endl;
		in_stack[u] = false;
		ctc[nrCtc-1].push_back(u);			
		while (u!=v && !s.empty())
		{
			u = s.top();
			in_stack[u] = false;		
			s.pop();
			ctc[nrCtc-1].push_back(u);				
		} 
	}
}	

int main()
{
	int x,y;
	freopen("ctc.in", "r", stdin);
	freopen ("ctc.out", "w", stdout);
	scanf("%d %d",&n,&m);
	in_stack.resize(n+1, false);
	graph.resize(n+1);
	lowlink.resize(n+1, -1);
	idx.resize(n+1, -1);
	for (int i = 1; i<=m; i++)
	{
		scanf("%d %d",&x,&y);
		graph[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		if (idx[i] == -1)
			tarjan (i);
	}
	cout<<ctc.size()<<"\n";
	for (int i = 0; i < ctc.size() ;i++)
	{
		for (int j = 0; j < ctc[i].size();j++)
			cout<<ctc[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}