Cod sursa(job #2195429)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 16 aprilie 2018 13:27:20
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
#include <vector>
#include <bitset>
using namespace std;
FILE *f,*g;
int st[100000];
bitset <100002> fr;
vector <int> ctc[100002];
int a[2][200002],v[100002],aGT[2][200002],vGT[100002];
int m,n,sol;
void read()
{   int i,j,k=0,kk=0;
    fscanf(f,"%d %d",&n,&m);
    for(int l=1; l<=m; l++)
    {
        fscanf(f,"%d %d",&i,&j);
        ++k;
        a[0][k]=j;
        a[1][k]=v[i];
        v[i]=k;
        ++kk;
        aGT[0][kk]=i;
        aGT[1][kk]=vGT[j];
        vGT[j]=kk;
    }
}
void dfs(int nod)
{   int ok;
    fr[nod]=1;
    ok=v[nod];
    while(ok)
    {
        if(!fr[a[0][ok]])
            dfs(a[0][ok]);
        ok=a[1][ok];
    }
    st[++st[0]]=nod;
}
void dfst(int nod)
{   int ok;
    fr[nod]=1;
    ok=vGT[nod];
    while(ok)
    {
        if(!fr[aGT[0][ok]])
            dfst(aGT[0][ok]);
        ok=aGT[1][ok];
    }
    ctc[sol].push_back(nod);
}
int main()
{   int i,j;
    f=fopen("ctc.in","r");
    g=fopen("ctc.out","w");
    read();
    for(i=1;i<=n;i++)
    {
        if(!fr[i])
            dfs(i);
    }
    for(i=1;i<=n;i++)
        fr[i]=0;
    for(i=n;i>=1;i--)
    {
        if(!fr[st[i]])
        {
            sol++;
            dfst(st[i]);
        }
    }
    fprintf(g,"%d\n",sol);
    for(i=1;i<=sol;i++)
    {
        for(j=0;j<ctc[i].size();j++)
            fprintf(g,"%d ",ctc[i][j]);
        fprintf(g,"\n");
    }
    fclose(f);
    fclose(g);
    return 0;
}