Cod sursa(job #3276108)

Utilizator Andrei_DruganDrugan Andrei Andrei_Drugan Data 12 februarie 2025 18:11:21
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <string.h>
#include <set>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m,x,y,viz[105],ct;
vector<int> v[105],vt[105],s;
set<int> rsp[105];

void dfs(int nod)
{
    viz[nod]=1;
    for(auto e:v[nod])
        if(!viz[e])
            dfs(e);
    s.emplace_back(nod);
}

void dfst(int nod)
{
    rsp[ct].insert(nod);
    viz[nod]=1;
    for(auto e:vt[nod])
        if(!viz[e])
            dfst(e);
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y;
        v[x].emplace_back(y);
        vt[y].emplace_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
            dfs(i);
    memset(viz,0,sizeof(viz));
    for(auto it=s.rbegin(); it!=s.rend(); it++)
        if(!viz[*it])
        {
            ct++;
            dfst(*it);
        }
    cout<<ct<<'\n';
    for(int i=1; i<=ct; i++,cout<<'\n')
        for(auto e:rsp[i])
            cout<<e<<' ';

}