Cod sursa(job #1920059)

Utilizator jordan1998Jordan jordan1998 Data 9 martie 2017 22:17:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
using namespace std;
#define pb push_back
int n,m,i,j,a,b,nrc=0;
bool viz1[100003],viz2[100003];
vector <int> g1[100003],g2[100003],g3[100003],st;
void dfs(int n)
{
   viz1[n]=true;
   st.pb(n);
   int i,x;
   x=g1[n].size();
   for(i=0;i<x;i++)
    if(!viz1[g1[n][i]])
    dfs(g1[n][i]);

}
void dff(int n)
{
   viz2[n]=true;
   g3[nrc].pb(n);
   int i,x;
   x=g2[n].size();
   for(i=0;i<x;i++)
    if(!viz2[g2[n][i]]&&viz1[g2[n][i]])
    dff(g2[n][i]);

}
int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        g1[a].pb(b);
        g2[b].pb(a);
    }
  for(i=1;i<=n;i++)
    if(!viz1[i]){dfs(i);
       a=st.size();
       for(j=0;j<a;j++)
        if(!viz2[st[j]]){ nrc++;dff(st[j]);}

    }
    g<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        a=g3[i].size();
        for(j=0;j<a;j++)
            g<<g3[i][j]<<" ";
        g<<'\n';
    }
}