Pagini recente » Cod sursa (job #610531) | Cod sursa (job #1737308) | Cod sursa (job #226869) | Cod sursa (job #2277648) | Cod sursa (job #2073329)
#include <bits/stdc++.h>
using namespace std;
int nxt;
vector <int> adj[100005];
vector < vector<int> > cmp;
vector <int> ax;
int disc[100005], low[100005];
bool viz[100005];
bool in_s[100005];
stack <int> s;
void dfs(int node){
++nxt;
disc[node] = low[node] = nxt;
viz[node] = 1;
in_s[node] = 1;
s.push(node);
for(auto it : adj[node]){
if(viz[it] == 0){
dfs(it);
}
low[node] = min(low[node], low[it]);
}
if(disc[node] == low[node]){
int u;
ax.clear();
do{
u = s.top();
in_s[u] = 0;
s.pop();
ax.push_back(u);
}while(u != node);
cmp.push_back(ax);
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,x,y;
fin>>n>>m;
for(i = 1;i <= m;i++){
fin>>x>>y;
adj[x].push_back(y);
}
for(i = 1;i <= n;i++){
if(viz[i] == 0){
dfs(i);
}
}
fout<<cmp.size()<<'\n';
for(auto v : cmp){
for(auto it : v){
fout<<it<<' ';
}
fout<<'\n';
}
}