Pagini recente » Cod sursa (job #533436) | Cod sursa (job #49561) | Cod sursa (job #461782) | Cod sursa (job #1442534) | Cod sursa (job #3229099)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 1e5;
const int INF = 1e9;
vector<int> G[NMAX + 1];
vector<int> GT[NMAX + 1];
int vis[NMAX + 1];
int vis2[NMAX + 1];
int timp = 0;
int ti[NMAX + 1], tf[NMAX + 1];
vector<int> ctc[NMAX + 1];
int nrctc;
void dfs(int node) {
vis[node] = 1;
timp++;
ti[node] = timp;
for(int i = 0; i < G[node].size(); i++) {
int vecin = G[node][i];
if(!vis[vecin]) {
dfs(vecin);
}
}
timp++;
tf[node] = timp;
}
void dfs2(int node) {
vis2[node] = 1;
ctc[nrctc].push_back(node);
for(int i = 0; i < GT[node].size(); i++) {
int vecin = GT[node][i];
if(!vis2[vecin]) {
dfs2(vecin);
}
}
}
bool cmp(pair<int, int> p1, pair<int, int> p2) {
// if(p1.second > p2.second) {
// return true;
// }
// return false;
return p1.second > p2.second;
}
int main() {
int n, m;
f >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
dfs(i);
}
}
vector<pair<int, int>> v;
for(int i = 1; i <= n; i++) {
v.push_back({i, tf[i]});
}
sort(v.begin(), v.end(), cmp);
for(int i = 0; i < v.size(); i++) {
if(!vis2[v[i].first]) {
nrctc++;
dfs2(v[i].first);
}
}
g << nrctc << '\n';
for(int i = 1; i <= nrctc; i++) {
for(int j = 0; j < ctc[i].size(); j++) {
g << ctc[i][j] << ' ';
}
g << '\n';
}
// for(int i = 1; i <= n; i++) {
// cout << ti[i] << ' ' << tf[i] << '\n';
// }
return 0;
}