Mai intai trebuie sa te autentifici.
Cod sursa(job #3252936)
| Utilizator | Data | 31 octombrie 2024 15:58:55 | |
|---|---|---|---|
| Problema | Componente tare conexe | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.16 kb |
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX = 100002;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
bitset <NMAX> f;
void dfs(int start, vector <vector<int>>& edges, vector <int>& add_to) {
f[start] = 1;
for(auto node : edges[start]) {
if(!f[node])
dfs(node, edges, add_to);
}
add_to.push_back(start);
}
int n;
vector <vector <int>> v, inv;
vector <vector <int>> ctc;
vector <int> st;
int main()
{
int m, a, b;
cin >> n >> m;
v.resize(n + 1);
inv.resize(n + 1);
for(int i = 1; i <= m; i++) {
cin >> a >> b;
v[a].push_back(b);
inv[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
if(!f[i])
dfs(i, v, st);
}
f = 0;
for(int i = st.size() - 1; i >= 0; i--) {
if(!f[st[i]]) {
ctc.push_back(vector<int>());
dfs(st[i], inv, ctc.back());
}
}
cout << ctc.size() << '\n';
for(int i = 0; i < ctc.size(); i++) {
for(auto node : ctc[i])
cout << node << " ";
cout << '\n';
}
return 0;
}
