Cod sursa(job #2272617)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 30 octombrie 2018 14:27:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <iostream>
#define DIMN 100001

using namespace std;
int g,sol,elem,niv[DIMN],low[DIMN],s[DIMN],f[DIMN];
vector <int> v[DIMN],sl[DIMN];
void dfs (int nod){
    int vecin,i;
    g++;
    niv[nod]=g;
    low[nod]=g;
    s[++elem]=nod;
    f[nod]=1;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (!niv[vecin]){
            dfs(vecin);
            low[nod]=min(low[nod],low[vecin]);
        }
        else if (f[vecin])
            low[nod]=min(low[nod],low[vecin]);
    }
    if (low[nod]==niv[nod]){
        sol++;
        do{
            sl[sol].push_back(s[elem]);
            f[s[elem]]=0;
            elem--;
        } while (s[elem+1]!=nod);
    }
}
int main()
{
    FILE *fin=fopen ("ctc.in","r");
    FILE *fout=fopen ("ctc.out","w");
    int n,m,x,y,i,j;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
    }
    for (i=1;i<=n;i++){
        if (!niv[i])
            dfs (i);
    }
    fprintf (fout,"%d\n",sol);
    for (i=1;i<=sol;i++){
        for (j=0;j<sl[i].size();j++)
            fprintf (fout,"%d ",sl[i][j]);
        fprintf (fout,"\n");
    }
    return 0;
}