Pagini recente » Cod sursa (job #2433461) | Cod sursa (job #3138384) | Cod sursa (job #1766038) | Cod sursa (job #2840646) | Cod sursa (job #1519205)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1;
const int MAX_M = 200000 + 1;
const int NIL = -1;
struct Graph
{
struct Edge
{
int v;
int urm;
};
Edge G[MAX_M];
int head[MAX_N];
int contor;
Graph() : contor(0) {
for (int i = 1; i < MAX_N; ++i)
head[i] = NIL;
}
void addEdge(int x, int y)
{
G[contor] = {y, head[x]};
head[x] = contor++;
}
};
Graph G, GT;
bool visited[MAX_N];
int sorted[MAX_N];
vector<vector<int>> ANS;
int N, M;
int dim = 0;
int getInt()
{
int x;
scanf("%d", &x);
return x;
}
void dfs(int node)
{
visited[node] = true;
for (int p = G.head[node]; p != NIL; p = G.G[p].urm)
{
int v = G.G[p].v;
if (!visited[v])
dfs(v);
}
sorted[ ++dim ] = node;
}
void dfsT(int node, vector<int> &ctc)
{
ctc.emplace_back(node);
visited[node] = false;
for (int p = GT.head[node]; p != NIL; p = GT.G[p].urm)
{
int v = GT.G[p].v;
if (visited[v])
dfsT(v, ctc);
}
}
void kosaraju()
{
for (int i = N; i >= 1; i--)
{
int node = sorted[i];
if (visited[node])
{
vector<int> ctc;
dfsT(node, ctc);
ANS.emplace_back(ctc);
}
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
N = getInt(); M = getInt();
for (int i = 1; i <= M; ++i)
{
int x, y;
x = getInt(); y = getInt();
G.addEdge(x, y);
GT.addEdge(y, x);
}
for (int i = 1; i <= N; ++i)
if (!visited[i])
dfs(i);
kosaraju();
printf("%d\n", (int)ANS.size());
for (size_t i = 0; i < ANS.size(); ++i)
{
for (int x : ANS[i])
printf("%d ", x);
printf("\n");
}
return 0;
}