Cod sursa(job #1131733)

Utilizator jul123Iulia Duta jul123 Data 1 martie 2014 11:19:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#define NR_MAX 100000
using namespace std;

vector<int>a[NR_MAX], ctc[NR_MAX];
int niv1[NR_MAX], niv2[NR_MAX], viz[NR_MAX], k=0, nr=0;
stack<int> st;

void dfs(int nod)
{
    int j, u;
    niv1[nod]=k;
    niv2[nod]=k;
    k++;
    st.push(nod);
    viz[nod]=1;
    for(j=0; j<a[nod].size(); j++) {
        u=a[nod][j];
        if(niv1[u]==-1) {
            dfs(u);
            niv2[nod]=min(niv2[nod], niv2[u]);
        }
        else
            if(viz[u]==1)
                niv2[nod]=min(niv2[nod], niv1[u]);
    }
    if(niv1[nod]==niv2[nod]) {
        do {
            j=st.top();
            viz[j]=0;
            st.pop();
            ctc[nr].push_back(j+1);
        }while(j!=nod);
        nr++;
    }
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("ctc.in", "r");
    fout=fopen("ctc.out", "w");

    int i, m, n, x, y, j;
    fscanf(fin, "%d %d", &n, &m);
    for(i=1; i<=m; i++) {
        fscanf(fin, "%d %d", &x, &y);
        a[x-1].push_back(y-1);
    }
    for(i=0; i<n; i++) {
        niv1[i]=-1;
        viz[i]=0;
    }
    for(i=0; i<n; i++)
        if(niv1[i]==-1)
            dfs(i);
    fprintf(fout, "%d\n", nr);
    for(i=0; i<nr; i++) {
        for(j=0; j<ctc[i].size(); j++)
            fprintf(fout, "%d ", ctc[i][j]);
        fprintf(fout, "\n");
    }
}