Cod sursa(job #1707894)

Utilizator traian.vidrascutraian vidrascu traian.vidrascu Data 26 mai 2016 02:02:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

vector<vector<int> > scc,gr;
int n,m,idx=1;
vector<int> index,low_index,in_stack,com;
stack<int> stiva;
void tarjan(int nod)
{
	int i,j;
	index[nod]=idx;
	low_index[nod]=idx;
	idx++;
	stiva.push(nod);
	in_stack[nod]=1;
	for(i=0;i<gr[nod].size();i++)
	{
		if(index[gr[nod][i]]==-1)
		{
			tarjan(gr[nod][i]);
			low_index[nod]=min(low_index[nod],low_index[gr[nod][i]]);
		}
		else 
		{
			if(in_stack[gr[nod][i]]==1)
			{
				low_index[nod]=min(low_index[nod],low_index[gr[nod][i]]);
			}
		}
	}
	if(low_index[nod]==index[nod])
	{
		int aux;
		com.clear();
		do
		{
			aux=stiva.top();
			stiva.pop();
			
			com.push_back(aux);
			in_stack[aux]=0;
		}
		while(aux!=nod);
		scc.push_back(com);
	}
	
}
int main()
{
	int i,j,x,y,z;
	f>>n>>m;
	gr.resize(n+1);
	index.resize(n+1,-1);
	low_index.resize(n+1,1000000);
	in_stack.resize(n+1);
	scc.clear();
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		
		gr[x].push_back(y);
	
		//in[y].push_back(x);
	}
	for(i=1;i<=n;i++)
	if(index[i]==-1)
		tarjan(i);
	g<<scc.size()<<"\n";
	for(i=0;i<scc.size();i++)
	{
		for(j=0;j<scc[i].size();j++)
			g<<scc[i][j]<<" ";
		g<<"\n";
	}
}