Cod sursa(job #2314903)

Utilizator dragossofiaSofia Dragos dragossofia Data 9 ianuarie 2019 11:24:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define N 100001
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
vector <int> ad[N],in[N],par,comp[N];
bool viz[N];
int n,m,ct;
void citire()
{fin>>n>>m;
 int i,x,y;
 for(i=1;i<=m;i++)
    {fin>>x>>y;
     ad[x].push_back(y);
     in[y].push_back(x);
    }
}

void topo(int nod)
{viz[nod]=1;
 for(int i=0;i<ad[nod].size();i++)
      if(!viz[ad[nod][i]])
            topo(ad[nod][i]);
 par.push_back(nod);
}

void dfs(int nod)
{viz[nod]=1;cout<<nod;
 comp[ct].push_back(nod);
 for(int i=0;i<in[nod].size();i++)
    if(!viz[in[nod][i]])
        {
         dfs(in[nod][i]);
        }

}
void rezolva()
{int i,j;
 for(i=1;i<=n;i++)
    if(!viz[i])topo(i);
 for(i=1;i<=n;i++)
    viz[i]=0;
 for(i=par.size()-1;i>=0;i--)
   {
    if(!viz[par[i]])
    {ct++;
     dfs(par[i]);
    }
   }
 fout<<ct<<"\n";
 for(i=1;i<=ct;i++)
    {for(j=0;j<comp[i].size();j++)
            fout<<comp[i][j]<<" ";
     fout<<"\n";
    }
}
int main()
{   citire();
    rezolva();
    return 0;
}