Mai intai trebuie sa te autentifici.
Cod sursa(job #2971503)
| Utilizator | Data | 27 ianuarie 2023 15:05:14 | |
|---|---|---|---|
| Problema | Componente tare conexe | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.2 kb |
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX = 1e5;
vector <int> g[NMAX + 1], rg[NMAX + 1], ans[NMAX + 1];
bitset <NMAX + 1> viz;
stack <int> stiva;
int ctc;
void dfs(int x){
viz[x] = 1;
for(auto y : g[x])
if(!viz[y])
dfs(y);
stiva.push(x);
}
void dfs2(int x){
viz[x] = 1;
ans[ctc].push_back(x);
for(auto y : rg[x])
if(!viz[y])
dfs2(y);
}
int main(){
int n = 0, m = 0;
cin >> n >> m;
for(int i = 0; i < m; i++){
int x = 0, y = 0;
cin >> x >> y;
g[x].push_back(y);
rg[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs(i);
viz = 0;
while(!stiva.empty()){
if(viz[stiva.top()]){
stiva.pop();
continue;
}
ctc++;
dfs2(stiva.top());
stiva.pop();
}
cout << ctc << "\n";
for(int i = 1; i <= ctc; i++){
sort(ans[i].begin(), ans[i].end());
for(auto y : ans[i])
cout << y << " ";
cout << "\n";
}
}