Pagini recente » Cod sursa (job #3360335) | Cod sursa (job #3360301) | Cod sursa (job #3360295) | Cod sursa (job #3360132) | Cod sursa (job #3360822)
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#define int long long
//#define int short
using namespace std;
const int nmax = 1e5;
int n, m, cnt = 0;
vector<int> adj[nmax + 5], radj[nmax + 5], top, comp[nmax + 5];
void dfstop(vector<int>& vis, int node){
vis[node] = 1;
for (auto& neinode : adj[node]){
if (!vis[neinode]){
dfstop(vis, neinode);
}
}
top.push_back(node);
}
void topologicalsort(){
vector<int> vis(n + 1, 0);
for (int i = 1; i <= n; i++){
if (!vis[i]){
dfstop(vis, i);
}
}
reverse(top.begin(), top.end());
}
void dfscomp(vector<int>& vis, int node){
vis[node] = 1;
for (auto& neinode : radj[node]){
if (!vis[neinode]){
dfscomp(vis, neinode);
}
}
comp[cnt].push_back(node);
}
void componenteconexe(){
vector<int> vis(n + 1, 0);
for (int i = 1; i <= n; i++){
if (!vis[top[i - 1]]){
cnt++;
dfscomp(vis, top[i - 1]);
}
}
cout<<cnt<<"\n";
for (int i = 1; i <= cnt; i++){
sort(comp[i].begin(), comp[i].end());
for (auto& j : comp[i]){
cout<<j<<" ";
}
cout<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdou);
cin>>n>>m;
while (m--){
int u, v;
cin>>u>>v;
adj[u].push_back(v);
radj[v].push_back(u);
}
topologicalsort();
componenteconexe();
}