Cod sursa(job #2265250)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 20 octombrie 2018 21:17:37
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

namespace Graph
{
    int N, M;
    int I, idx[100005], low[100005], done[100005];
    vector<int> now, edg[100005];
    vector< vector<int> > scc;

    void addEdge(int x, int y)  { edg[x].push_back(y); }

    void DFS(int nod)
    {
        if(idx[nod] || done[nod])    return;
        idx[nod] = ++I;
        low[nod] = idx[nod];

        for(auto nxt: edg[nod])
            if(!done[nxt])
            {
                DFS(nxt);
                low[nod] = min(low[nod], low[nxt]);
            }

        now.push_back(nod);
        if(low[nod] == idx[nod])
        {
            for(auto &x: now)   done[x] = 1;
            scc.push_back(now);
            now.clear();
        }
    }

    void computeSCC()
    {
        scc.clear();
        I = 0;
        for(int i = 1; i <= N; i++) low[i] = idx[i] = done[i] = 0;
        now.clear();
        for(int i = 1; i <= N; i++) DFS(i);

        printf("%d\n", scc.size());
        for(auto &v: scc)
        {
            for(auto &x: v) printf("%d ", x);
            printf("\n");
        }
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("scc.in", "r", stdin);
    freopen("scc.out", "w", stdout);
    #endif

    using namespace Graph;

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addEdge(x, y);
    }

    computeSCC();

    return 0;
}