Cod sursa(job #3353862)

Utilizator Andreea3425Diaconu Andreea Andreea3425 Data 12 mai 2026 10:38:19
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

bool dfs(int a, int k, vector <vector <int>>& v1, vector <int>& f){
    int i;

    if (a==k)
        return true;

    f[a]=1;
    for (i=0; i<v1[a].size(); i++)
        if (f[v1[a][i]]==0 && dfs(v1[a][i], k, v1, f))
            return true;

    return false;
}

bool path(int a, int k, vector <vector <int>>& v1){
    vector <int> f(v1.size()+1, 0);
    return dfs(a, k, v1, f);
}

vector <vector <int>> fid(int n, vector <vector <int>>& a){
    int i,j;

    vector <vector <int>> r;
    vector <int> f(n+1, 0);
    vector <vector <int>> v1(n+1);

    for (i=0; i<a.size(); i++)
        v1[a[i][0]].push_back(a[i][1]);

    for (i=1; i<=n; i++)
        if (f[i]==0){
            vector <int> rr;
            rr.push_back(i);

            for (j=i+1; j<=n; j++)
                if (f[j]==0 && path(i, j, v1) && path(j, i, v1)){
                    f[j]=1;
                    rr.push_back(j);
                }

            r.push_back(rr);
        }

    return r;
}


signed main()
{
    ifstream cin ("ctc.in");
    ofstream cout ("ctc.out");

    int n,m,i,a,b,j;

    cin >> n >> m;

    vector <vector <int>> v;

    for (i=0; i<m; i++){
        cin >> a >> b;
        v.push_back({a, b});
    }

    vector <vector<int>> r=fid(n, v);

    cout << r.size() << '\n';
    for (i=0; i<r.size(); i++){
        for (j=0; j<r[i].size(); j++)
            cout << r[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}