Cod sursa(job #2265233)

Utilizator ShootingHorseHorsie Horse ShootingHorse Data 20 octombrie 2018 21:01:33
Problema Componente tare conexe Scor 30
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#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;
}