Cod sursa(job #2232433)

Utilizator TrixerAdrian Dinu Trixer Data 19 august 2018 06:01:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <list>

using namespace std;

#define NMAX 100001
#define UNDEFINED 0

struct node
{
	int index;
	int lowlink;
	bool onStack;
};

int n, m, index, count;
vector<int> graph[NMAX];
stack<int> s;
list<int> sccs[NMAX];
node v[NMAX];

void dfs(int x)
{
	// mark current node
	v[x].index = index;
	v[x].lowlink = index;
	v[x].onStack = true;
	s.push(x);
	index++;

	// visit successors
	for (int i : graph[x]) {
		if (v[i].index == UNDEFINED) {
			dfs(i);
			v[x].lowlink = min(v[x].lowlink, v[i].lowlink);
		} else if (v[i].onStack)
			v[x].lowlink = min(v[x].lowlink, v[i].index);
	}

	// if x is a root node, emit an SCC
	if (v[x].index == v[x].lowlink) {
		int y;

		do {
			y = s.top();
			s.pop();
			v[y].onStack = false;
			sccs[count].push_front(y);
		} while (x != y);

		count++;
	}
}

void tarjan()
{
	index = 1;

	for (int i = 1; i <= n; i++)
		if (v[i].index == UNDEFINED)
			dfs(i);
}

int main()
{
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	// read input
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x].push_back(y);
	}

	// solve
	tarjan();

	// print output
	printf("%d\n", count);
	for (int i = 0; i < count; i++) {
		for (int j : sccs[i])
			printf("%d ", j);
		printf("\n");
	}

	return 0;
}