Cod sursa(job #3032323)

Utilizator 2080Cristian 2080 Data 21 martie 2023 22:17:46
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;

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


vector<vector<int>> l(100001);
vector<vector<int>> lt(100001);
int n,m;
vector<vector<int>> comp;
queue<int> q={};
int visited[100001] ={0};

void dfs1(int x) {
    if (visited[x] == 0) {
        visited[x] = 1;
        for (const auto &item: l[x]) {
            if (visited[item] == 0) {
                dfs1(item);
            }

        }
        q.push(x);
    }
}

void dfs2(int x,vector<int>&c) {
    if (visited[x] == 0) {
        c.push_back(x);
        visited[x] = 1;
        for (const auto &item: l[x]) {
            if (visited[item] == 0) {
                dfs2(item,c);
            }

        }
    }
}


int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        l[x].push_back(y);
        lt[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        dfs1(i);
    }
    memset(visited, 0, 100000);
    int cnt = 0;
    while (!q.empty()) {
        int k = q.front();
        q.pop();
        if (visited[k] == 0) {
            cnt += 1;
            vector<int> cc;
            dfs2(k, cc);
            comp.push_back(cc);
        }

    }
    fout<<cnt;
    for (const auto &item: comp) {
        fout<<endl;
       for (const auto &item1: item) {
            fout<<item1<<" ";

       }

    }
}