Mai intai trebuie sa te autentifici.
Cod sursa(job #2684412)
Utilizator | Data | 13 decembrie 2020 17:36:00 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 2.69 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 >> k;
G = GT = vector<vector<int>>(n + 1);
for(int i = 1; i <= m; i++){
fin >> x >> y; G[x].push_back(y); GT[y].push_back(x);
}
}
//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;
}