Codeforces Round #285 (Div. 2) C. Misha and Forest

Problem link – http://codeforces.com/contest/501/problem/C

This is an interesting graph problem 🙂

Since the graph is acyclic, there will be leave(s) (with degree = 1). Identify those leaves. Consider a leaf i.Its xor value (let it be j) will directly give you its neighbour(since xor of a number is the number itself).Add (i,j) as an edge to the ans vector. Now decrement the degree of the node j and also apply xor to j’s xor sum value to remove i. After removing leaf i from the forest, the forest will still remain a forest . So similarly find the leaves in the current forest (and also the edges which is why we are doing this) and carefully prune the leaves until the forest becomes empty.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;
	int main(){
	int n,v,s;
	vector<pair<int,int> > arr,ans;
	scanf("%d",&n);
	vector<int>leaves;
	REP(i,n){
	scanf("%d%d",&v,&s);
	arr.pb(mp(v,s));
	if(v==1)
	leaves.pb(i);
	}
	int l=0;
	while(l<leaves.size()){
	if(arr[leaves[l]].first==1){
	ans.pb(mp(leaves[l],arr[leaves[l]].second));
	arr[arr[leaves[l]].second].first--;
	if(arr[arr[leaves[l]].second].first==1)
	leaves.pb(arr[leaves[l]].second);
	arr[arr[leaves[l]].second].second^=leaves[l];
	arr[leaves[l]].first--;
	}
	l++;
	}
	printf("%d\n",ans.size());
	REP(i,ans.size()){
	printf("%d %d\n",ans[i].first,ans[i].second);
	}
	}

view raw Misha and Forest.cpp hosted with ❤ by GitHub

Spoj(CAM5) Prayatna PR

A simple DFS will do good.A 2D vector is used to represent the graph via adjacency list.

All you have to do is have a visited array to mark nodes in the graph that is already visited. Have a count variable to count the number of groups available.

	#include<iostream>
	#include<cstdio>
	#include<vector>
	#include<cstring>
	using namespace std;
	bool visited[100005];
	vector<vector<int> > adj(100005);
	int n;
	void dfs(int i){
	if(visited[i])
	return;
	visited[i]=1;
	for(vector<int>::iterator it=adj[i].begin();it!=adj[i].end();it++){
	if(!visited[*it])
	dfs(*it);
	}
	}
	int main(){
	int t;
	scanf("%d",&t);
	while(t--){
	int e,ans=0,x,y;
	scanf("%d %d",&n,&e);
	memset(visited,0,sizeof visited);
	for(int i=0;i<n;i++)
	adj[i].clear();
	for(int i=0;i<e;i++){
	scanf("%d %d",&x,&y);
	adj[x].push_back(y);
	adj[y].push_back(x);
	}
	for(int i=0;i<n;i++){
	if(!visited[i]){
	ans++;
	dfs(i);
	}
	}
	printf("\n%d",ans);
	}
	}

view raw CAM5.cpp hosted with ❤ by GitHub