Cod sursa(job #1139461)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 11 martie 2014 10:33:40
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <stack>
#define minim(a,b) (a<b)?(a):(b)
#define nmax 100005
using namespace std;

vector <int> g[nmax];
vector <int> r[nmax];
stack <int> stk;
int low[nmax];
int index[nmax];
bool viz[nmax];
int n,m;
int nr;

int tarjan(int start) {
    stk.push(start);
    low[start] = index[start] = stk.size();
    viz[start] = true;
    for (vector <int> :: iterator it = g[start].begin(); it != g[start].end();it++) {
        if (viz[*it]) low[start] = minim(low[start],low[*it]);
        else {
            int tj = tarjan(*it);
            low[start] = minim(low[start],tj);
        }
    }
    if (low[start] == index[start]) {
        nr++;
        while (stk.top() != start) {
            r[nr].push_back(stk.top());
            stk.pop();
        }
        stk.pop();
        r[nr].push_back(start);
    }
    return low[start];
}

int main() {
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
    }
    for (int i=1;i<=n;i++) if (!viz[i]) tarjan(i);
    printf("%d\n",nr);
    for (int i=1;i<=nr;i++) {
        for (vector <int> ::iterator it = r[i].begin();it != r[i].end();it++) printf("%d ",*it);
        printf("\n");
    }
}