Cod sursa(job #3252932)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 31 octombrie 2024 15:55:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;

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

vector< int > v[100001], vt[100001];
vector< int > st;
bool vis[100001];
vector< vector<int> > ctc; 

void dfs(int nod, int t){
    if(t == 0){ // facem ST pe graful ne-transpus
        vis[nod] = 1;
        for(int i = 0; i < v[nod].size(); i++){
            if(!vis[ v[nod][i] ]) dfs( v[nod][i], t );
        }
        st.push_back( nod );
    }else{
        vis[nod] = 1;
        ctc.back().push_back(nod);
        for(int i = 0; i < vt[nod].size(); i++){
            if(!vis[ vt[nod][i] ]){
                dfs(vt[nod][i], t);
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; in >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; in >> a >> b;
        v[a].push_back(b);
        vt[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        if(vis[i] == 0) dfs(i, 0);
    }

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

    for(int i = 0; i <= 100000; i++) vis[i] = 0;
    for(int i = st.size() - 1; i >= 0; i--){
        if(!vis[ st[i] ]){
            vector<int> l;
            ctc.push_back(l);
            dfs(st[i], 1);
        }
    }

    // cout << "ctc : \n";
    out << ctc.size() << '\n';
    for(int i = 0; i < ctc.size(); i++){
        sort( ctc[i].begin(), ctc[i].end() );
        for(int j = 0; j < ctc[i].size(); j++) out << ctc[i][j] << " ";
        out << '\n';
    }

    return 0;
}