Cod sursa(job #2324686)

Utilizator ceciliamariciucCecilia Mariciuc ceciliamariciuc Data 21 ianuarie 2019 12:36:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <stack>
#include <vector>
#define nmax 100001

using namespace std;

FILE *f,*g;

int n,m;
bool viz1[nmax],viz2[nmax];
stack <int> S;
vector <int> V[nmax];
vector <int> Vt[nmax];
vector <int> V2[nmax];

void Citire()
{int i,x,y;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
    {fscanf(f,"%d%d",&x,&y);
     V[x].push_back(y); Vt[y].push_back(x);
    }
}

void DFS1(int x)
{int i;
vector <int>::iterator it;
viz1[x]=1;
for(it=V[x].begin();it!=V[x].end();it++)
     if(!viz1[*it]) DFS1(*it);
S.push(x);
}

void DFS2(int x, int k)
{int i;
vector <int>::iterator it;
viz2[x]=1;
for(it=Vt[x].begin();it!=Vt[x].end();it++)
    if(!viz2[*it]) DFS2(*it,k);
V2[k].push_back(x);
}


int main()
{int c,k=0,i;
vector <int>::iterator it;
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
Citire();
fclose(f);
for(i=1;i<=n;i++)
    if(viz1[i]==0) DFS1(i);
while(!S.empty())
    {c=S.top(); S.pop();
      if(viz2[c]==0)
         {k++; DFS2(c,k);}
    }
fprintf(g,"%d",k);
fprintf(g,"\n");
for(i=1;i<=n;i++)
   {for(it=V2[i].begin();it!=V2[i].end();++it)
        fprintf(g,"%d ",*it);
    fprintf(g,"\n");
   }
    return 0;
}