Cod sursa(job #2214600)

Utilizator bebeetarepredescu bebeetare Data 19 iunie 2018 14:23:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,i,j,nr,x,y;
bool marker1[100002],marker2[100002];
vector <int > a[100002],q2[100002],b[100002],q1;
void ceva2(int x)
{
    marker2[x]=true;
    for(int i=0;i<b[x].size();i++)
    {
        if(marker2[b[x][i]]==false)
        {
            ceva2(b[x][i]);
        }
    }
    q2[nr].push_back(x);
}
void ceva1(int x)
{
    marker1[x]=true;
    for(int i=0;i<a[x].size();i++)
    {
        if(marker1[a[x][i]]==false)
        {
            ceva1(a[x][i]);
        }
    }
    q1.push_back(x);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(marker1[i]==false)
        {
            ceva1(i);
        }
    }

    reverse(q1.begin(),q1.end());
    for (int i = 0; i < n; i++)
    {
        if (!marker2[q1[i]])
        {
            nr++;
            ceva2(q1[i]);
        }
    }
    g<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        for(j=0;j<q2[i].size();j++)
        {
            g<<q2[i][j]<<" ";
        }
        g<<'\n';
    }
    return 0;
}