Cod sursa(job #2343617)

Utilizator serbandonceanSerban Doncean serbandoncean Data 14 februarie 2019 09:46:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;ifstream fin("ctc.in");ofstream fout("ctc.out");vector <int>g[100009];vector <int>afis[100009];vector <int>gt[100009];int  uz[100009];int i,lg,nr,n,j,m;int s[100009];void citire();void dfs(int k);void dfs1(int k);void reset();int main(){citire();for(i=1; i<=n; i++)if(!uz[i])dfs(i);reset();while(lg>0){if(!uz[s[lg]]){nr++;dfs1(s[lg]);}lg--;}fout<<nr<<'\n';for(i=1; i<=nr; i++){for(j=0;j<afis[i].size();j++)fout<<afis[i][j]<<' ';fout<<'\n';}return 0;}void citire(){int i,j,x,y;fin>>n>>m;for(i=1; i<=m; i++){fin>>x>>y;g[x].push_back(y);gt[y].push_back(x);}}void dfs(int k){int i;uz[k]=1;for(i=0; i<g[k].size(); i++)if(!uz[g[k][i]]){dfs(g[k][i]);}s[++lg]=k;}void dfs1(int k){int i;uz[k]=nr;afis[nr].push_back(k);for(i=0; i<gt[k].size(); i++)if(!uz[gt[k][i]]){dfs1(gt[k][i]);}}void reset(){int i;for(i=0; i<100009; i++)uz[i]=0;}