Cod sursa(job #2668314)

Utilizator anamaria2602Avram Ana Maria anamaria2602 Data 4 noiembrie 2020 19:28:41
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define maxi 100003
int n, m, postordine[maxi], x, cnt, nr, y, viz[maxi];
vector < int > M[maxi];
vector < int > M_T[maxi];
vector < int > afis[maxi];
vector < int > ::iterator it;

void dfs1(int x)
{
    viz[x] = 1;
    for ( it = M[x].begin(); it != M[x].end(); it ++ )
        if ( viz[*it] == 0)
            dfs1(*it);
    postordine[++nr] = x;
}
void dfs2(int x)
{
    afis[cnt].push_back(x);
    viz[x] = 0;
    for( it = M_T[x].begin(); it != M_T[x].end(); it ++ )
        if ( viz[*it] )
            dfs2(*it);
}

int main()
{
    f >> n >> m ;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        f >> x >> y;
        M[x].push_back(y);
        M_T[y].push_back(x);
    }
    for ( int i = 1; i <= n; i ++ )
        if ( viz[i] == 0)
            dfs1(i);
    for ( int i = n; i >= 1; i --)
        if ( viz[postordine[i]])
        {
            cnt ++;
            dfs2(postordine[i]);
        }
    g << cnt << '\n';
    for ( int i = 1; i <= cnt; i ++ )
    {
        for ( it = afis[i].begin(); it != afis[i].end(); it ++ )
            g << *it << " ";
        g << '\n';
    }
    return 0;
}