Mai intai trebuie sa te autentifici.
Cod sursa(job #2976593)
Utilizator | Data | 9 februarie 2023 17:49:23 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.13 kb |
#include <bits/stdc++.h>
using namespace std;
const int nmx = 1e5 + 5;
#if 1
#define cin fin
#define cout fout
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#endif // 0
vector<int> ad[nmx], tad[nmx];
vector<int> tsort,viz(nmx);
vector<vector<int>> ccx;
void SortT(int k){
viz[k] = 1;
for(int to : ad[k])
if(viz[to] == 0)
SortT(to);
tsort.push_back(k);
}
void dfs(int k){
viz[k] = 1;
ccx.back().push_back(k);
for(int to : tad[k]){
if(viz[to] == 0)
dfs(to);
}
}
int main(){
int n,m;
cin >> n >> m;
while(m--){
int u,v;
cin >> u >> v;
ad[u].push_back(v);
tad[v].push_back(u);
}
for(int i=1;i<=n;i++)
if(viz[i]==0)
SortT(i);
fill(viz.begin(),viz.end(),0);
reverse(tsort.begin(),tsort.end());
for(int nd : tsort){
if(viz[nd]==0){
ccx.push_back({});
dfs(nd);
}
}
cout << ccx.size() << "\n";
for(auto& cx : ccx){
for(int el : cx)
cout << el << " ";
cout << "\n";
}
}