Mai intai trebuie sa te autentifici.

Cod sursa(job #2472552)

Utilizator MartinDimitrovMartin Dimitrov MartinDimitrov Data 12 octombrie 2019 16:26:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 100;

vector<int> adj[maxn];
vector<int> adjInv[maxn];
vector<int> dfs;

bool used[maxn];
int value[maxn];

vector<int> components[maxn];

void DFS(int v){
    if(used[v]) return;
    used[v] = true;
    for(int i=0; i<adj[v].size(); i++){
        DFS(adj[v][i]);
    }
    dfs.push_back(v);
}

void DFSvalue(int v, int val){
    if(value[v]!=0) return;
    value[v]=val;
    components[val].push_back(v);
    for(int i=0; i<adjInv[v].size(); i++){
        DFSvalue(adjInv[v][i], val);
    }
}

int main()
{
    int n;
    int m;

    cin >> n >> m;

    for(int i=0; i<m; i++){
        int first, second;
        cin >> first >> second;

        adj[first].push_back(second);
        adjInv[second].push_back(first);
    }

    for(int i=0; i<n; i++){
        if(used[i]) continue;
        DFS(i);
    }

    int valueNumber = 1;

    for(int i=dfs.size()-1; i>=0; i--){
        if(value[dfs[i]]!=0) continue;
        DFSvalue(dfs[i], valueNumber);
        valueNumber++;
    }

    cout << valueNumber-1 << endl;

    for(int i=1; i<valueNumber; i++){
        for(int j=0; j<components[i].size(); j++){
            cout << components[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}
/*
10 12
0 1
1 2
2 3
3 1
2 4
4 5
5 6
6 4
5 7
7 6
8 4
8 9
*/