Cod sursa(job #2334028)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 2 februarie 2019 10:35:14
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

vector<int> v[NMAX];
vector<int> sol[NMAX];

FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");

int n,m,x,y,viz[NMAX],st[NMAX],nr,nrctc,ll[NMAX],idx[NMAX],index;

void df(int k) {
    int i,u,x;
    viz[k]=1;
    idx[k]=ll[k]=++index;
    st[++nr]=k;
    for (i=0;i<v[k].size();++i) {
        u=v[k][i];
        if (!idx[u]) {
            df(u);
            ll[k]=min(ll[u],ll[k]);
        }
        else if (viz[u])
            ll[k]=min(ll[u],ll[k]);
    }
    if (ll[k]==idx[k]) {
        ++nrctc;
        do {
            x=st[nr--];
            viz[x]=0;
            sol[nrctc].push_back(x);
        }while (x!=k);
    }
}

int main() {
    int i,j;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;++i) {
        fscanf(f,"%d%d",&x,&y);
        v[x].push_back(y);
    }
    for (i=1;i<=n;++i)
        if (!idx[i]) df(i);

    fprintf(g,"%d\n",nrctc);
    for (i=1;i<=nrctc;++i) {
        for (j=0;j<sol[i].size();j++)
            fprintf(g,"%d ",sol[i][j]);
        fprintf(g,"\n");
    }

    return 0;
}