Pagini recente » Cod sursa (job #2136535) | Cod sursa (job #1255049) | Cod sursa (job #1198683) | Cod sursa (job #1521375) | Cod sursa (job #2928607)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int nmax = 100005;
int n, m, x, y, tmp, ans;
vector<int> G[nmax];
vector<vector<int>> sol;
stack<int> Q;
int low[nmax], dt[nmax];
bool viz[nmax], smb[nmax];
void DFS(int node){
viz[node] = 1;
low[node] = dt[node] = tmp++;
Q.push(node);
smb[node] = 1;
for(auto x:G[node]){
if(!viz[x]){
DFS(x);
low[node] = min(low[node], low[x]);
}
else if(smb[x])
low[node] = min(low[node], low[x]);
}
if(low[node] == dt[node]){
vector<int> a;
ans++;
while(!Q.empty() && Q.top() != node){
a.push_back(Q.top());
smb[Q.top()] = 0;
Q.pop();
//cout<<w<<" ";
}
a.push_back(Q.top());
smb[Q.top()] = 0;
Q.pop();
//cout<<w<<"\n";
sol.push_back(a);
}
}
int main(){
f >> n >> m;
for(int i = 1; i <= m; ++i){
f >> x >> y;
G[x].push_back(y);
}
for(int i = 1; i <= n; ++i)
if(!viz[i])
DFS(i);
g << ans << "\n";
for(int i = 0; i < ans; ++i){
for(auto bt:sol[i])
g << bt << ' ';
g << "\n";
}
return 0;
}