Cod sursa(job #2155137)

Utilizator calin1Serban Calin calin1 Data 7 martie 2018 17:14:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
#define N 100005

using namespace std;

int n, m, lowlink[N], index[N], nr, global_index = 1;

vector <int> G[N];

vector <int> componente[N];

stack <int> S;

bitset <N> viz;

bitset <N> in_stack;

void afisare()
{
    printf("%d\n", nr);

    for(int i = 0 ; i < nr ; ++i)
    {
        for(int j = 0 ; j < componente[i].size() ; ++j)
        {
            printf("%d ", componente[i][j]);
        }

        printf("\n");
    }
}

void dfs(int nod)
{
    index[nod] = global_index;

    lowlink[nod] = index[nod];

    global_index++;

    viz[nod] = true;

    S.push(nod);

    in_stack[nod] = true;

    vector <int>::iterator it;

    for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
    {
        if(!viz[*it])
        {
            dfs(*it);

            lowlink[nod] = min(lowlink[nod] , lowlink[*it]);
        }
        else
        {
            if(in_stack[*it])
            {
                lowlink[nod] = min(lowlink[nod] , lowlink[*it]);
            }
        }
    }

    if(lowlink[nod] == index[nod])
    {
        int x;

        do
        {
            x = S.top();

            in_stack[x] = false;

            S.pop();

            componente[nr].push_back(x);

        }while(x != nod);

        nr++;
    }
}

void solve()
{
    for(int i = 1 ; i <= n ; ++i)
    {
        if(!viz[i])
        {
            dfs(i);
        }
    }
}

void citire()
{
    scanf("%d %d\n", &n, &m);

    int a, b;

    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d\n", &a, &b);

        G[a].push_back(b);
    }

    solve();

    afisare();
}

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

    citire();

    return 0;
}