Cod sursa(job #1551233)

Utilizator GooggaIoana Iaru Googga Data 15 decembrie 2015 15:57:53
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 10005;
vector <int> G[NMAX];
vector <int> S, dfs_discover, dfs_low, articulation_vertex, dfs_parent, visited,SCC[NMAX];
int t, dfsRoot, rootChildren, n, numSCC;

void articulationPoint(int u) {
    int j, v;
    ++t;
    dfs_discover[u] = dfs_low[u] = t;
    for (j = 0; j < G[u].size(); ++j) {
        v = G[u][j];
        if (!dfs_discover[v]) {
            dfs_parent[v] = u;
            if (u == dfsRoot)
                rootChildren++;

            articulationPoint(v);
            if (dfs_low[v] >= dfs_discover[u])
                articulation_vertex[u] = true;
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
        } else {
            if (v != dfs_parent[u])
                dfs_low[u] = min(dfs_low[u], dfs_discover[v]);
        }
    }
}

void tarjanSCC(int u) {
    dfs_low[u] = dfs_discover[u] = ++t;
    S.push_back(u); //stores u in a vector based on visitation order
    visited[u] = 1;
    for (int j = 0; j < (int) G[u].size(); j++) {
        int v = G[u][j];
        if (!dfs_discover[v])
            tarjanSCC(v);
        if (visited[v]) //condition for update
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
    }
    if (dfs_low[u] == dfs_discover[u]) {
        //if this is a root of an SCC
        ++numSCC;
        while (1) {
            int v = S.back();
            S.pop_back();
            visited[v] = 0;
            SCC[numSCC].push_back(v);
     if (u == v)
                break;
        }
    }
}

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

    int m, u, v, i;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    dfs_parent.assign(n + 1, -1);
    articulation_vertex.assign(n + 1, 0);
    dfs_low.assign(n + 1, 0);
    dfs_discover.assign(n + 1, 0);
    for (i = 1; i <= n; ++i)
        if (!dfs_discover[i]) {
            dfsRoot = i;
            rootChildren = 0;
            articulationPoint(i);
            articulation_vertex[dfsRoot] = (rootChildren > 1);
        }
 
    dfs_discover.assign(n + 1, 0);
    dfs_low.assign(n + 1, 0);
    visited.assign(n + 1, 0);
    t = numSCC = 0;
    for (i = 1; i <= n; i++)
        if (dfs_discover[i] == 0)
            tarjanSCC(i);

    printf("%d", numSCC);
    printf("\n");
   for(i=1;i<=numSCC;i++)
    {
        int nr=SCC[i].size();
        for(int j=0;j<nr;j++)
            printf("%d ", SCC[i][j]);
        printf("\n");
   }
    return 0;
}