Cod sursa(job #2684417)

Utilizator Silviu45Dinca Silviu Silviu45 Data 13 decembrie 2020 17:39:23
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.66 kb
//ctc1 : Roy and Floyd Warshall O(n^3)
//ctc2 : Plus minus O(n^2)
//ctc3 : Kosaraju O(n+m)

//joi-26 noiembrie 2020
//This is ctc3 - Kosaraju
//#3421 ctck - pbinfo.ro
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

//store under adiacent list form
vector <vector< int> > G,GT;
stack <int> elements;
vector <int> visited(125);
int n,m,k,x,y;//nodul k,perechi x->y

void read(){
    fin >> n >> m;
    G = GT = vector<vector<int>>(n + 1);
    for(int i = 1; i <= m; i++){
        fin >> x >> y; G[x].push_back(y);
	}
}

//DFS-ul pt generarea stivei
void generare_stiva(int nod){
    visited[nod] = 1;
    //parcurgem lista de adiacenta a nodului "nod"
    for(int i = 0; i < G[nod].size(); i++){
        //bool arc = (count(G[nod].begin(),G[nod].end(),i) == 1);//daca apare i in lista de adiacenta a nodului curent
        if(!visited[G[nod][i]])
            generare_stiva(G[nod][i]);
    }
    //partea 4 din dfs , inseram in stiva
    elements.push(nod);
}

vector <int> visited2(125);
int cc = 0;

//dfs normal
void DFS(int nod){
    visited2[nod] = cc;
    //parcurgem lista de adiacenta a nodului "nod"
    for(int i = 0; i < GT[nod].size(); i++){
        //bool arc = (count(GT[nod].begin(),GT[nod].end(),i) == 1);
        if(!visited2[GT[nod][i]])
            DFS(GT[nod][i]);
    }
}

void solve(){
    //luam fiecare nod din stiva si incepem un DFS din el
    fill(visited2.begin() , visited2.end() , 0);
    while(!elements.empty()){
        int nod_curent = elements.top();
        if(!visited2[nod_curent]){
            cc++;
            DFS(nod_curent);
        }
        //cout << elements.top() << " ";
        elements.pop();
    }
    fout << cc << "\n";
    for(int comp = 1; comp <= cc; comp++){
        for(int nod = 1; nod <= n; nod++){
            if(visited2[nod] == comp)
                fout << nod << " ";
        }
        fout << "\n";
    }
    //for(int i = 1; i <= n; i++){
    //    cout << visited2[i] << " ";
    //}
    //visited[k] - componenta conexa a lui k


    /*int cnt = 0;
    for(int i = 1; i <= n; i++)
        if(visited2[i] == visited2[k])
            cnt++;
    cout << cnt;*/
}

int main()
{
    read();
    //generare_stiva(1);
    //generam stiva doar din dfs-uri pe 1 dar e aiurea , pt ca poate dfs-ul din 1 imi merge doar pe 1 , 2 ,3
    //pe urma eu celelalte noduri nu le mai am pe stiva
    //in stiva am nevoie de toate nodurile
    //fuck fuck fuck
    for(int nod = 1; nod <= n; nod++){
        if(!visited[nod])
            generare_stiva(nod);
    }
    solve();
    fin.close();
    fout.close();
    return 0;
}