Cod sursa(job #2125553)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 8 februarie 2018 15:53:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100005

using namespace std;

int N, M, indexGlobal = 1, nrSol;
struct nod
{
    int index, lowlink;
    bool inStack;
} v[NMAX];
vector <int> G[NMAX], sol[NMAX];
stack <int> S;

void read()
{
    scanf("%d %d", &N, &M);
    for(int i=1; i<=M; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
    }
}

void dfs(int node)
{
    v[node].index = indexGlobal;
    v[node].lowlink = indexGlobal;
    indexGlobal++;
    S.push(node);
    v[node].inStack = true;
    vector <int>::iterator it;

    for(it = G[node].begin(); it != G[node].end(); ++it)
        if(v[*it].index == 0)
        {
            dfs(*it);
            v[node].lowlink = min(v[node].lowlink, v[*it].lowlink);
        }
        else if(v[*it].inStack == true)
            v[node].lowlink = min(v[node].lowlink, v[*it].index);

    if(v[node].index == v[node].lowlink)
    {
        while(S.top() != node)
        {
            v[S.top()].inStack = false;
            sol[nrSol].push_back(S.top());
            S.pop();
        }
        sol[nrSol].push_back(S.top());
        S.pop();
        v[node].inStack = false;
        nrSol++;
    }
}

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

void print()
{
    printf("%d\n", nrSol);
    for(int i=0; i<nrSol; ++i)
    {
        vector <int>::iterator it;
        sort(sol[i].begin(), sol[i].end());
        for(it = sol[i].begin(); it != sol[i].end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    read();
    solve();
    print();
    return 0;
}