Cod sursa(job #2195455)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 16 aprilie 2018 13:50:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <stdio.h>
#include <deque>
#include <bitset>
#include <cstring>
#include <vector>

using namespace std;
FILE *f,*g;

int start1[100002],start2[100002];///dimensiunea=nr de noduri;
int t1[3][400002],t2[3][400002];///dimensiunea 2*nr de muchii
int succesor[100002],predecesor[100002],tot;
deque <int> q;
bitset <100002> viz1;
bitset <100002> viz2;
vector <int> vecini[100002];

void dfs1(int nod)
{
    int no;
    viz1[nod]=1;
    no=start1[nod];
    while(no)
    {
        if(!viz1[t1[0][no]])
            dfs1(t1[0][no]);
        no=t1[1][no];

    }
    q.push_back(nod);
}
void dfs2(int nod)
{
    int no;
    viz2[nod]=1;
    no=start2[nod];
    while(no)
    {
        if(!viz2[t2[0][no]])
            dfs2(t2[0][no]);
        no=t2[1][no];

    }
     vecini[tot].push_back(nod);
}

int main()
{
    int n,m,i,j,k1=0,o,cont,k2=0;
    f=fopen("ctc.in","r");
    g=fopen("ctc.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(o=1;o<=m;++o)
    {
        fscanf(f,"%d %d",&i,&j);
        ++k1;
        t1[0][k1]=j,t1[1][k1]=start1[i],start1[i]=k1;
        ++k2;
        t2[0][k2]=i,t2[1][k2]=start2[j],start2[j]=k2;
    }

    for(i=1;i<=n;++i)
        if(!viz1[i])
            dfs1(i);
    /*while(!q.empty())
    {
        x=q.front();
        fprintf(g,"%d ",x);
        q.pop_front();
    }*/
    int x;
    while(!q.empty())
    {
        x=q.back();
        q.pop_back();
        if(!viz2[x])
            dfs2(x),++tot;
    }
    fprintf(g,"%d\n",tot);
    for(i=0;i<tot;++i)
    {
        for(j=0;j<vecini[i].size();++j)
            fprintf(g,"%d ",vecini[i][j]);
        fprintf(g,"\n");
    }



    fclose(f);
    fclose(g);
    return 0;
}