Cod sursa(job #2265257)

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

using namespace std;

#define FILE_IO

namespace Graph
{
    int N, M;
    int I, idx[100005], low[100005], instk[100005];
    vector<int> stk, 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])    return;
        idx[nod] = ++I;
        low[nod] = idx[nod];
        instk[nod] = 1;
        stk.push_back(nod);

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

        if(low[nod] == idx[nod])
        {
            now.clear();
            while(!stk.empty() && stk.back() != nod)
            {
                now.push_back(stk.back());
                instk[stk.back()] = 0;
                stk.pop_back();
            }
            now.push_back(nod);
            instk[nod] = 0;
            stk.pop_back();
            scc.push_back(now);
        }
    }

    void computeSCC()
    {
        scc.clear();
        I = 0;
        for(int i = 1; i <= N; i++) low[i] = idx[i] = 0;
        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("ctc.in", "r", stdin);
    freopen("ctc.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;
}