Pagini recente » Cod sursa (job #2175806) | Monitorul de evaluare | Cod sursa (job #861953) | Cod sursa (job #2110165) | Cod sursa (job #1610752)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int knmax = 100005;
int n, m;
vector<int> graph[knmax];
vector<vector<int> > ans;
void read(){
ifstream in("ctc.in");
in >> n >> m;
int x, y;
for(int i = 0; i < m; ++i){
in >> x >> y;
graph[x].push_back(y);
}
}
bool vis[knmax], instk[knmax];
int ind[knmax], dp[knmax];
vector<int> stk;
int index;
void dfs(int x){
vis[x] = true;
ind[x] = index;
dp[x] = index;
++index;
stk.push_back(x);
instk[x] = true;
for(int i = 0; i < graph[x].size(); ++i)
if(!vis[graph[x][i]]) {
dfs(graph[x][i]);
dp[x] = min(dp[x], dp[graph[x][i]]);
} else if (instk[graph[x][i]])
dp[x] = min(dp[x], ind[graph[x][i]]);
if(ind[x] == dp[x]) {
vector<int> add;
while(stk.back() != x) {
add.push_back(stk.back());
instk[stk.back()] = false;
stk.pop_back();
}
add.push_back(stk.back());
instk[stk.back()] = false;
stk.pop_back();
ans.push_back(add);
}
}
void solve(){
for(int i = 1; i <= n; ++i)
if(!vis[i])
dfs(i);
}
void write(){
ofstream out("ctc.out");
out << ans.size() << "\n";
for(int i = 0; i < ans.size(); ++i){
for(int j = 0; j < ans[i].size(); ++j)
out << ans[i][j] << " ";
out << "\n";
}
}
int main () {
read();
solve();
write();
}