Cod sursa(job #3348992)

Utilizator Cristian2007Tanase Cristian-Gabriel Cristian2007 Data 24 martie 2026 22:27:56
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include "bits/stdc++.h"
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int l[102],l1[102];
int nr;
vector<int> v1[102],v2[102];
stack<int> s;
vector<int>comp[200001];
void dfs (int nod)
{
    int x;
    l[nod]=1;
    for (x=0;x<v1[nod].size();x++)
    {
        if (l[v1[nod][x]]==0)
        {
            dfs(v1[nod][x]);
        }
    }
    //g<<nod<<" ";
    s.push(nod);
}
void dfs1 (int nod)
{
    int x;
    l1[nod]=1;
    for (x=0;x<v2[nod].size();x++)
    {
        if (l1[v2[nod][x]]==0)
        {
            dfs1(v2[nod][x]);
        }
    }
comp[nr].push_back(nod);
    //s.push(nod);
}
int main ()
{
    int n,m,x,i,j;
    f>>n>>m;
    for (x=1;x<=m;x++)
    {
        f>>i>>j;
        v1[i].push_back(j);
        v2[j].push_back(i);
    }
    for (x=1;x<=n;x++)
    {
        if (l[x]==0)
        {
            dfs(x);
        }
    }


    nr=0;
    while (s.size())
    {
        x=s.top();s.pop();
        if (l1[x]==0)
        {
            dfs1(x);
            nr++;
        }
    }
    //cout<<s.size();
    /*while(s.size()>0)
    {
         cout<<s.top();
         s.pop();
    }*/
    g<<nr<<"\n";
    for(i=0;i<nr;i++)
    {
       for(j=0;j<comp[i].size();j++)
        g<<comp[i][j]<<" ";
       g<<"\n";
    }
    return 0;
}