Cod sursa(job #3341138)

Utilizator bogdan_.f2Fulga Bogdan bogdan_.f2 Data 18 februarie 2026 10:33:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
vector<int>L[100001],G[100001],st,cnc[100001];
vector<bool>v,v2;
int nrc=0,n,in=0;
void citire()
{
    int m;
    ifstream f("ctc.in");
    f>>n>>m; int x,y;
    st.resize(n+1,0);
    v.resize(n+1,false);
    for(int i=1; i<=m; i++)
    {

        f>>x>>y;
        L[x].push_back(y);
        G[y].push_back(x);
    }
    f.close();
}
void dfs1(int k)
{
    v[k]=true;
    for(auto e:L[k])
        if(v[e]==false)
            dfs1(e);
    st[++in]=k;
}
void dfs2(int k)
{
    v[k]=false;
    for(auto e:G[k])
        if(v[e]==true)
            dfs2(e);
    cnc[nrc].push_back(k);
}
void ctc()
{
    for(int i=1; i<=n; i++)
        if(v[i]==false)
            dfs1(i);
    for(int i=n; i>=1; i--)
        if(v[st[i]]==true)
        {
            nrc++;
            dfs2(st[i]);


        }
}
void afisare()
{
    ofstream g("ctc.out");
    g<<nrc<<'\n';
    for(int i=1; i<=nrc; i++)
    {
        sort(cnc[i].begin(),cnc[i].end());
        for(auto e:cnc[i])
            g<<e<<" ";
        g<<'\n';
    }
    g.close();
}
int main()
{
    citire();
    ctc();
    afisare();
    return 0;
}