Cod sursa(job #2790395)

Utilizator BriannaBrianna Stan Brianna Data 28 octombrie 2021 21:20:43
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> s[100002],p[100002];
vector<int> fin[100002];
bool viz[100002];
vector<int> sort_top;
int n,m,nr=0;
void dfs_s(int x)
{
    viz[x]=true;
    for(auto y:s[x])
    {
        if(!viz[y])
        {
            dfs_s(y);
        }
    }
    sort_top.push_back(x);
}
void dfs_p(int x)
{
    viz[x]=0;
    for(auto y:p[x])
    {
     if(viz[y])
     {
         dfs_p(y);
     }
    }
    fin[nr].push_back(x);
}
int main() {
    in>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b;
        s[a].push_back(b);
        p[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if (!viz[i]) {
            dfs_s(i);
        }
    }
    for(int i=n-1;i>=0;i--)
    {
        if(viz[sort_top[i]])
        {
            nr++;
            dfs_p(sort_top[i]);
        }
    }
    out<<nr<<endl;
    for(int i=1;i<=nr;i++)
    {
        for(auto it:fin[i])
            out<<it<<" ";
        out<<endl;
    }
    return 0;
}