Cod sursa(job #3194199)

Utilizator lucriLuchian Cristian lucri Data 17 ianuarie 2024 11:32:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,nr,x,y;
vector<vector<int>>a,b,r;
stack<int>s;
bool v[100010],v2[100010];
void stiva(int n)
{
    v[n]=true;
    for(auto x:a[n])
    {
        if(v[x]==false)
            stiva(x);
    }
    s.push(n);
    return;
}
void raspuns(int n)
{
    v2[n]=true;
    r[nr].push_back(n);
    for(auto x:b[n])
    {
        if(v2[x]==false)
            raspuns(x);
    }
    return;
}
int main()
{
    in>>n>>m;
    a.resize(n+5);
    b.resize(n+5);
    r.resize(n+5);
    for(int i=1;i<=m;++i)
    {
        in>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
    {
        if(v[i]==false)
            stiva(i);
    }
    while(!s.empty())
    {
        int i=s.top();
        s.pop();
        if(v2[i]==false)
        {
            ++nr;
            raspuns(i);
        }
    }
    out<<nr;
    for(int i=1;i<=nr;++i)
    {
        out<<'\n';
        for(auto x:r[i])
        {
            out<<x<<' ';
        }
    }
    return 0;
}