Pagini recente » Cod sursa (job #1732399) | Cod sursa (job #128479) | Cod sursa (job #2063661) | Cod sursa (job #1498647) | Cod sursa (job #2265233)
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100000
#define MAX_EDGES 200001
#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
struct edge_t {
int node;
int next;
} edges[MAX_EDGES];
int graph[MAX_NODES], edge_it = 1;
int stack[MAX_NODES], stack_it = 0;
int vis[MAX_NODES], low[MAX_NODES], time;
int comp[2*MAX_NODES], comp_it, nr_comp;
bool on_stack[MAX_NODES];
void add_edge(int x, int y)
{
edges[edge_it] = (struct edge_t){y, graph[x]};
graph[x] = edge_it++;
}
void dfs(int node)
{
struct edge_t edge = edges[graph[node]];
vis[node] = time++;
low[node] = vis[node];
stack[stack_it++] = node;
on_stack[node] = true;
while (edge.node) {
if (!vis[edge.node]) {
dfs(edge.node);
low[node] = MIN(low[node], low[edge.node]);
} else if (on_stack[edge.node]) {
low[node] = MIN(low[node], vis[edge.node]);
}
edge = edges[edge.next];
}
if (low[node] == vis[node]) {
nr_comp++;
int neighbour;
do {
neighbour = stack[--stack_it];
on_stack[neighbour] = false;
comp[comp_it++] = neighbour;
} while (neighbour != node);
comp_it++;
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m, x, y;
scanf("%d %d", &n, &m);
while (m--) {
scanf("%d %d", &x, &y);
add_edge(x, y);
}
for (int i = 1; i <= n; i++) {
if (!vis[i])
dfs(i);
}
printf("%d\n", nr_comp);
for (int i = 0; i < comp_it; i++) {
if (comp[i])
printf("%d ", comp[i]);
else
printf("\n");
}
return 0;
}