Cod sursa(job #1754870)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 8 septembrie 2016 21:22:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 100000;
const int MMAX = 200000;

int index;
int Min[NMAX+5];
int ind[NMAX+5];
bool instack[NMAX+5];
int st[NMAX+5], Size;

vector <int> v[NMAX+5];

int comp;
vector <int> ans[NMAX+5];

void dfs(int nod)
{
    ind[nod] = index;
    Min[nod] = index;
    instack[nod] = true;
    index++;
    st[Size++] = nod;
    for(int i=0; i<v[nod].size(); i++)
    {
        if(ind[v[nod][i]] == 0)
        {
            dfs(v[nod][i]);
            Min[nod] = min(Min[nod], Min[v[nod][i]]);
        }
        else if(instack[v[nod][i]])
        {
            Min[nod] = min(Min[nod], Min[v[nod][i]]);
        }
    }
    if(Min[nod] == ind[nod])
    {
        int top;
        do
        {
            Size--;
            top = st[Size];
            instack[top] = false;
            ans[comp].push_back(top);
        }
        while(Size>=0 && top!=nod);
        comp++;
    }
}

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 x, y;
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
    }
    index = 1;
    for(int i=1; i<=n; i++)
        if(ind[i] == 0)
            dfs(i);
    printf("%d\n", comp);
    for(int i=0; i<comp; i++)
    {
        for(int j=0; j<ans[i].size(); j++)
            printf("%d ", ans[i][j]);
        printf("\n");
    }
    return 0;
}