Cod sursa(job #2317004)

Utilizator Username01Name Surname Username01 Data 12 ianuarie 2019 17:44:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <deque>
#include <vector>

using namespace std;
FILE *f,*g;
int n,m;
int starttr[100002],start[100002],t[2][200002],ttr[2][200002],sol;
bool viz[100002];
int q[100002];
vector <int> a[100002];

void dfstr(int nod)
{
    int poz,vecin;
    viz[nod]=1;
    poz=starttr[nod];
    while(poz)
    {
        vecin=ttr[0][poz];
        if(!viz[vecin])
            dfstr(vecin);
        poz=ttr[1][poz];
    }
    a[sol].push_back(nod);

}
void dfs(int nod)
{
    int poz,vecin;
    poz=start[nod];
    viz[nod]=1;
    while(poz)
    {
        vecin=t[0][poz];
        if(!viz[vecin])
            dfs(vecin);

        poz=t[1][poz];
    }
    q[++q[0]]=nod;
}
int main()
{
    f=fopen("ctc.in","r");
    g=fopen("ctc.out","w");
    fscanf(f,"%d %d",&n,&m);
    int k1=0,k2=0,x,y;
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d",&x,&y);
        t[0][++k1]=y;
        t[1][k1]=start[x];
        start[x]=k1;
        ttr[0][++k2]=x;
        ttr[1][k2]=starttr[y];
        starttr[y]=k2;
    }
    for(int i=1;i<=n;++i)
        if(!viz[i])
            dfs(i);
    for(int i=1;i<=n;++i)
        viz[i]=0;
    for(int i=n;i>=1;--i)
        if(!viz[q[i]])
            ++sol,dfstr(q[i]);
    fprintf(g,"%d\n",sol);
    for(int i=1;i<=sol;++i)
    {
        for(int j=0;j<a[i].size();++j)
            fprintf(g,"%d ",a[i][j]);
        fprintf(g,"\n");
    }
    fclose(f);
    fclose(g);
    return 0;
}