Cod sursa(job #2120942)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 3 februarie 2018 10:01:59
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAX = 100000;

int n, m;
vector <int> graf[MAX];
int index[MAX], lowIndex[MAX];
int onStack[MAX];
int GlobalIndex = 1;
stack <int> S;
vector <int> sol[MAX];
int counter;

void citire()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		graf[x].push_back(y);
	}
}

void dfs(int x)
{
	index[x] = lowIndex[x] = GlobalIndex;
	GlobalIndex++;
	S.push(x);
	onStack[x] = 1;
	
	for(auto e : graf[x])
	{
		if(index[e] == 0)
		{
			dfs(e);
			lowIndex[x] = min(lowIndex[x], lowIndex[e]);
		}
		else
			if(onStack[e])
				lowIndex[x] = min(lowIndex[x], index[e]);
	}
	if(lowIndex[x] == index[x])
	{
		int w;
		do
		{
			w = S.top();
			S.pop();
			onStack[w] = 0;
			sol[counter].push_back(w);
		}while(w != x);
		counter++;
	}
}

void tarjan()
{
	for(int i = 1; i <= n; i++)
		if(index[i] == 0)
			dfs(i);
}

void afisare()
{
	printf("%d\n", counter);
	for(int i = 0; i < counter; i++)
	{
		for(int e : sol[i])
			printf("%d ", e);
		printf("\n");
	}
}

int main()
{
	freopen("../ctc.in", "r", stdin);
	freopen("../ctc.out", "w", stdout);
	citire();
	tarjan();
	afisare();
	return 0;
}