Cod sursa(job #2289957)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 25 noiembrie 2018 16:05:39
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

int niv[100010];
int low[100010];
int inst[100010];
vector<int> g[100010];
vector<int> r[100010];
int st[100010];
int lst, lr;
int ind;

void dfs(int nod)
{
    st[lst++] = nod;
    niv[nod] = ++ind;
    low[nod] = niv[nod];
    inst[nod] = 1;
    for(auto next : g[nod])
    {
        if(niv[next] == 0)
        {
            dfs(next);
            low[nod] = min(low[nod], low[next]);
        }
        else if(inst[nod])
            low[nod] = min(low[nod], low[next]);
    }
    if(niv[nod] == low[nod])
    {
        st[lst] = -1;
        while(st[lst] != nod)
        {
            r[lr].push_back(st[lst - 1]);
            inst[st[lst - 1]] = 0;
            lst--;
        }
        lr++;
    }
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
    }
    for(int i = 1; i <= n; i++)
    {
        if(niv[i] == 0)
        {
            dfs(i);
        }
    }
    printf("%d\n", lr);
    for(int i = 0; i < lr; i++)
    {
        for(int j = 0; j < r[i].size(); j++)
            printf("%d ", r[i][j]);
        printf("\n");
    }
    return 0;
}