Pagini recente » Cod sursa (job #1894434) | Cod sursa (job #2545147) | Cod sursa (job #3256256) | Cod sursa (job #2349018) | Cod sursa (job #782654)
Cod sursa(job #782654)
#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
const int knmax = 100005;
class santa{
private:
int verts, edges, index, vis[knmax], dp[knmax];
vector<int> graph[knmax];
vector<pair<int, int> > stack;
vector<vector<pair<int, int> > > sol;
vector<int> ans;
public:
void init(){
assert(freopen("santa.in", "r", stdin));
scanf("%d%d",&verts,&edges);
for(int i = 1; i <= edges; ++i){
int x, y;
scanf("%d%d", & x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
}
for(int i = 1; i <= verts; ++i)
vis[i] = dp[i] = 0;
index = 0;
}
int min(int x, int y){
if(x < y)
return x;
return y;
}
void dfs(int x){
++index;
vis[x] = dp[x] = index;
for(int i = 0; i < graph[x].size(); ++i)
if(vis[graph[x][i]]){
if(vis[x] > vis[graph[x][i]])
dp[x] = min(dp[x], vis[graph[x][i]]);
}
else{
stack.push_back(make_pair(x, graph[x][i]));
dfs(graph[x][i]);
dp[x] = min(dp[x], dp[graph[x][i]]);
if(dp[graph[x][i]] >= vis[graph[x][i]]){
vector<pair<int, int> > com;
while(stack.back() != make_pair(x, graph[x][i])){
com.push_back(stack.back());
stack.pop_back();
}
com.push_back(stack.back());
stack.pop_back();
sol.push_back(com);
}
}
}
void build(){
}
void road(){
}
void solve(){
}
void show(){
assert(freopen("santa.out", "w", stdout));
if(ans.size() == 0){
printf("No chance"); //nice try tho
return;
}
printf("%d\n",ans.size());
for(int i = 0 ; i < ans.size(); ++i)
printf("%d ", ans[i]);
}
} t;
int main(){
t.init();
t.dfs(1);
t.build();
t.road();
t.solve();
t.show();
return 0;
}