Cod sursa(job #1501059)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 12 octombrie 2015 23:01:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define NMAX 100007

using namespace std;
int n, m, a, b, stiva[NMAX], cap = 0, low[NMAX], t[NMAX], ct = 1, update, ap[NMAX];
vector <int> adj[NMAX];
struct raspuns
{
    vector<int> el;
} tmp;
vector <raspuns> sol;
void tarjan(int nod)
{
    ++cap;
    stiva[cap] = nod;
    t[nod] = ct;
    low[nod] = ct;
    ++ct;
    ap[nod] = update;
    int sze = adj[nod].size();
    for(int i = 0; i< sze; ++i)
    {
        if(ap[adj[nod][i]] != ap[nod]) continue;
        if(low[adj[nod][i]] && low[adj[nod][i]] < low[nod]) low[nod] = low[adj[nod][i]];
    }
    for(int i = 0; i< sze; ++i)
    {
        if(!ap[adj[nod][i]])
        {
            tarjan(adj[nod][i]);
            if(low[adj[nod][i]] && low[adj[nod][i]] < low[nod]) low[nod] = low[adj[nod][i]];
        }
    }
    if(t[nod] == low[nod])
    {
        tmp.el.clear();
        while(stiva[cap] != nod)
        {
            tmp.el.push_back(stiva[cap]);
            --cap;
        }
        tmp.el.push_back(stiva[cap]);
        --cap;
        sol.push_back(tmp);
    }
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(; m; --m)
    {
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
    }
    for(int i = 1; i<= n; ++i)
    {
        if(!ap[i])
        {
            ++update;
            tarjan(i);
        }
    }
    int sze = sol.size();
    printf("%d\n", sze);
    for(int i = 0; i< sze; ++i)
    {
        int sze1 = sol[i].el.size();
        for(int j = 0; j< sze1; ++j)
        {
            printf("%d ", sol[i].el[j]);
        }
        printf("\n");
    }
    return 0;
}