Pagini recente » Cod sursa (job #545339) | Cod sursa (job #1567554) | Cod sursa (job #1287454) | Cod sursa (job #1892388) | Cod sursa (job #2232433)
#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;
}