Cod sursa(job #2103364)

Utilizator GeoeyMexicanuBadita George GeoeyMexicanu Data 10 ianuarie 2018 01:31:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int st[100010],i,k,j,n,m,nr,viz[100010],viz1[100010],x,y;
vector<int> vec[100010];
vector<int> vecr[100010];
vector<int> ans[100010];
void dfs(int x)
{
    viz[x]=1;
    for(int t=0;t<vec[x].size();t++)
        if(viz[vec[x][t]]==0)
            dfs(vec[x][t]);
    st[++k]=x;
}
void dfs1(int x)
{
    viz1[x]=1;
    ans[nr].push_back(x);
    for(int t=0;t<vecr[x].size();t++)
        if(viz1[vecr[x][t]]==0)
        {
            dfs1(vecr[x][t]);
        }
}
int main()
{
    f>>n>>m;
    while(m!=0)
    {
        f>>x>>y;
        vec[x].push_back(y);
        vecr[y].push_back(x);
        m--;
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i);
    for(i=k;i>=1;i--)
    {
        if(viz1[st[i]]==0)
        {
            nr++;
            dfs1(st[i]);
        }
    }
    g<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        for(j=0;j<ans[i].size();j++)
        {
            g<<ans[i][j]<<' ';
        }
        g<<'\n';
    }
}