Cod sursa(job #1610049)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 23 februarie 2016 11:19:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int low[100010], niv[100010], N, M, x, y, a, nr;

vector<int>L[100010], SOL[100010];
bitset<100010>v, X;
deque<int>Q;

void dfs(int nod)
{
    v[nod] = 1;
    X[nod] = 1;
    Q.push_back(nod);
    low[nod] = niv[nod] = ++a;

    for(int i = 0; i < L[nod].size(); i ++)
    {
        if(v[ L[nod][i] ] == 0)
        {
            dfs(L[nod][i]);
            low[nod] = min(low[nod], low[ L[nod][i] ]);
        }
        else
        {
            if(X[ L[nod][i] ] == 1)
            {
                low[nod] = min(low[nod], low[ L[nod][i] ]);
            }
        }
    }
    if(low[nod] == niv[nod])
    {
        nr ++;
        while(Q.back() != nod)
        {
            int b = Q.back();
            Q.pop_back();
            SOL[nr].push_back(b);
            X[b] = 0;
        }
        Q.pop_back();
        SOL[nr].push_back(nod);
        X[nod] = 0;
    }
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i ++)
    {
        fin >> x >> y;
        L[x].push_back(y);
    }

    for(int i = 1; i <= N; i ++)
    {
        if(v[i] == 0)
        {
            dfs(i);
        }
    }

    fout << nr << '\n';

    for(int i = 1; i <= nr; i ++)
    {
        for(int j = 0; j < SOL[i].size(); j ++)
        {
            fout << SOL[i][j] << " ";
        }
        fout << '\n';
    }

    return 0;
}