Cod sursa(job #1686843)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 12 aprilie 2016 14:34:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

int N, M, K;
int idx;
int indx[100005], instv[100005], low[100005];

vector <int> edg[100005];
vector < vector <int> > scc;
stack <int> stv;

void tarjan(int nod)
{
    indx[nod] = ++idx;
    low[nod] = idx;
    instv[nod] = 1;
    stv.push(nod);

    for(auto it = edg[nod].begin(); it != edg[nod].end(); it++)
    {
        int nxt = (*it);
        if(!indx[nxt])
        {
            tarjan(nxt);
            low[nod] = min(low[nod], low[nxt]);
        }
        else if(indx[nxt] && instv[nxt])
            low[nod] = min(low[nod], low[nxt]);
    }

    if(low[nod] == indx[nod])
    {
        vector <int> ctc;
        while(!stv.empty())
        {
            int nd = stv.top();
            ctc.push_back(nd);
            stv.pop();
            instv[nd] = 0;
            if(nd == nod)
                break;
        }
        scc.push_back(ctc);
    }
}

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

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edg[x].push_back(y);
    }

    idx = 0;
    for(int i = 1; i <= N; i++)
        if(!indx[i])
            tarjan(i);

    printf("%d\n", scc.size());
    for(int i = 0; i < scc.size(); i++, printf("\n"))
        for(int j = 0; j < scc[i].size(); j++)
            printf("%d ", scc[i][j]);

    return 0;
}