Cod sursa(job #1881636)

Utilizator stefan_gheorgheGheorghe Stefan stefan_gheorghe Data 16 februarie 2017 17:13:09
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> L1[200003],L2[200003];
long long nr,k=0,n,m,x,y,st[200003],mem[200003];
bool sel1[200003],sel2[200003];
void load(){f>>n>>m;for(int i=1;i<=m;i++) f>>x>>y,L1[x].push_back(y),L2[y].push_back(x);}
void dfs (int x,bool sel[200003],vector <int> L[200003])
{
    sel[x]=true;st[++k]=x;
    for(int i=0;i<L[x].size();i++)if(!sel[L[x][i]])dfs(L[x][i],sel,L);
}
int main()
{
    load();nr=0;
    for(int i=1;i<=n;i++)
        if(!sel1[i])
            dfs(i,sel1,L1);
    x=k;y=k+1;
    for (int i=1;i<=x;i++)
        if (!sel2[st[i]])
            {
                nr++,dfs(st[i],sel2,L2);
                mem[nr]=y;y=k+1;
            }
    g<<nr<<'\n';
    for (int i=1;i<nr;i++)
    {for (int j=mem[i];j<mem[i+1];j++) g<<st[j]<<' ';g<<'\n';}
    for (int i=mem[nr];i<=k;i++) g<<st[i]<<' ';
    return 0;
}