Cod sursa(job #3296204)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 12 mai 2025 10:06:37
Problema Componente tare conexe Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
#define in  fin
#define out fout

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector<int> g[100001], gt[100001];
bool m[100001];

vector<int> st;
vector< vector<int> > ctc;

void dfs(int nod, int f, bool care){
    m[nod] = 1;
    if(care == 0){ // st
        for(const int & x : g[nod]){
            if(!m[x]){
                m[x] = 1;
                dfs(x, nod, care);
            }
        }
        st.push_back(nod);
    }else{
        //cout << "is la " << nod << '\n';
        if(f == -1) ctc.push_back({});
        ctc.back().push_back(nod);
        for(const int & x : gt[nod]){
            if(!m[x]){
                m[x] = 1;
                dfs(x, nod, care);
            }
        }
    }
}

int main()
{
    int n, _m; in >> n >> _m;
    for(int i = 0; i < _m; i++){
        int a, b; in >> a >> b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }

    dfs(1, -1, 0);
    //cout << "st : ";
    //for(int i = 0; i < st.size(); i++) cout << st[i] << " ";
    //cout << '\n';

    for(int i = 0; i <= n; i++) m[i] = 0;

    for(int i = st.size() - 1; i >= 0; i--){
        if(m[ st[i] ]) continue;
        //cout << "nou\n";
        dfs(st[i], -1, 1);
    }

    out << ctc.size() << '\n';
    for(int i = 0; i < ctc.size(); i++){
        for(int j = 0; j < ctc[i].size(); j++) out << ctc[i][j] << " ";
        out << '\n';
    }

    return 0;
}

/*
5 4
1 2
2 3
1 3
5 4
*/