Cod sursa(job #782621)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 28 august 2012 14:25:33
Problema Santa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#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;
}