Cod sursa(job #1730930)

Utilizator mariakKapros Maria mariak Data 17 iulie 2016 20:52:37
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
#define Vmax 100002
#define pb(x) push_back(x)
#define Emax 2 * Nmax
#define NIL -1
FILE *fin  = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);

using namespace std;
int V, E, st[Vmax], disc[Vmax], low[Vmax], nscc;
vector <int> G[Vmax];
vector <int> sol[Vmax];
bitset <Vmax> onSt;
void read()
{
    int u, v;
    scanf("%d %d", &V, &E);
    while(E --)
    {
        scanf("%d %d", &u, &v);
        G[u].pb(v);
    }
}
int Min(int x, int y)
{
    return x < y ? x : y;
}
void DFS(int u, int depth)
{
    int v;
    disc[u] = low[u] = depth;
    st[++ st[0]] = u;
    onSt.set(u);

    int sz = G[u].size();
    for(int i = 0; i < sz; ++ i)
    {
        v = G[u][i];
        if(disc[v] == NIL)
        {
            DFS(v, depth + 1);
            low[u] = Min(low[u], low[v]);
        } /// forward (tree) edge
        else if(onSt.test(v) == 1)
            low[u] = Min(low[u], low[v]); /// back edge
        /// else we encounter a cross edge which should be avoid
    }
    if(low[u] == disc[u]) /// root of subtree
    {
        ++ nscc;
        do
        {
            v = st[st[0] --];
            onSt.reset(v);
            sol[nscc].pb(v);

        }while(v != u);
    }
}
void solve()
{
    int i;
    for(i = 1; i <= V; ++ i)
    {
        disc[i] = NIL;
    }
    for(i = 1; i <= V; ++ i)
    {
        if(disc[i] == NIL)
            DFS(i, 0);
    }
}
void write()
{
    printf("%d\n", nscc);
    for(int i = 1; i <= nscc; ++ i)
    {
        int sz = sol[i].size();
        for(int j = 0; j < sz; ++ j)
            printf("%d ", sol[i][j]);
        printf("%\n");
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}