193 - Graph Coloring

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 193 Graph Coloring

Post by @li_kuet » Fri Aug 17, 2012 10:16 pm

Try this Input who are getting WA :)
Input :

Code: Select all

3

5 0

8 4
1 2
3 4
5 6
6 8

2 1
1 2
Output :

Code: Select all

5
1 2 3 4 5
5
2 4 5 7 8
1
2

hover1178
New poster
Posts: 3
Joined: Mon Jan 21, 2013 11:57 am

Re: 193 Graph Coloring

Post by hover1178 » Sat Feb 23, 2013 3:49 pm

Hi Everyone,

Below is my code for this problem. It uses simple Breadth first search. Moreover, for each node, it tries to color it both white and black(assuming adjacent node is not black). I have no idea why my output in not right. I will be grateful if someone could take a look and tell what is wrong with my code. If you tell me mistake, it will motivate me to solve more problems and becoem better. PLEASE HELP

Code: Select all

#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<iostream>
#include<sstream>
using namespace std;
#define INF (1<<30)
vector<vector<int>> adjList;
class StoreAns{
	public:
		int count ;
		string seq ;
};

StoreAns findMax(queue<int> q, char color[],vector<int> d){
	
	int v = q.front();q.pop();
	bool any = false;
	for(int i = 0 ; i < adjList[v].size();i++){
		int k = adjList[v][i];
		if(d[k] == INF){
			any = true;
			q.push(k);
			color[k] = 'w';
			d[k] = d[v] + 1;
			StoreAns a1 = findMax(q,color,d);
			if(color[v] != 'b'){
				color[k] = 'b';
				StoreAns a2 = findMax(q,color,d);
				a2.count  = a2.count + 1;
				if(a1.count > a2.count) return a1;
				std::stringstream storestringnum;
				storestringnum << (k+1);
				a2.seq = storestringnum.str()+ " " + a2.seq;
				return a2;


			}else return a1;


		}//end inf chk
		

	}
	if(!any) {
		StoreAns temp;
		temp.count = 0;
		
		temp.seq = "";
		return temp;

	}


}

StoreAns printMaxBlack(int nn){
	vector<int> d(adjList.size(), INF);
	d[0] = 0;
	char color[105];
	queue<int> q; q.push(0); color[0] = 'w';
	StoreAns a1 = findMax(q,color,d);
	color[0] = 'b';
	StoreAns a2 = findMax(q,color,d); a2.count = a2.count+1;
	if(a1.count > a2.count) return a1;
	std::stringstream storestringnum;
	storestringnum << 1;
	a2.seq = storestringnum.str() + " " + a2.seq;
	return a2;
	

}

int main(){
	//string r = "";
	//int num = 100;
	//char x[21];
	//std::stringstream storestringnum;
	//storestringnum << num;
	//
	//string y = storestringnum.str() + " " + r;
	//cout<<"The concat is: " << y;
	freopen("in.txt","r",stdin);
	for(int i = 0 ; i < 105;i++) adjList.push_back(vector<int>());
	int ng,nn,ne,n1,n2;
	scanf("%d",&ng);
	for(int x = 0 ; x < ng; x++){
		scanf("%d %d",&nn,&ne);
		for(int i = 0 ; i < nn;i++) adjList[i].clear();
		for(int i = 0; i < ne; i++){
			scanf("%d %d",&n1,&n2);
			adjList[n1-1].push_back(n2-1);
			adjList[n2-1].push_back(n1-1);
		}
		StoreAns temp = printMaxBlack(nn);
		printf("The answer is: %d\n",temp.count);
		cout<<temp.seq<<endl;

	}//end tc for



	return 0;

}

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 193 Graph Coloring

Post by AKJ88 » Sat Feb 23, 2013 9:30 pm

@problemsolve I don't know why but I used dfs got WA then tried using backtracking and even though I thought I might get TLE got AC!:)

Can anyone explain why? Specially if you've solved it using BFS or DFS and got AC? Thanks.

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

Re: 193 Graph Coloring

Post by alexiago » Fri Aug 09, 2013 12:25 am

I first tried to solve this problem based on DFS, trying all initial possibilities as black, visiting all nodes and verifying if any neighbour was black before painting. But this approach was not covering all possibilities, for example, we can have a scenario where two white nodes in a row could lead us to more black nodes than one white and the other black.
For this reason, I tried another approach and got AC with backtracking, using basically the same logic we have to generate all permutations, so unlike DFS I'm not visiting neighbour nodes, nodes are visited according to their index, generating all possibilities. I also added some pruning constraints, like stopping if the number of remaining nodes to visit cannot reach the maximum number of black nodes or if the number of black nodes is equal the number of nodes.
I hope this can help.

dhruba07
New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

Re: 193 Graph Coloring

Post by dhruba07 » Sat Mar 29, 2014 7:26 am

AC :)
Last edited by dhruba07 on Fri Apr 04, 2014 6:21 am, edited 1 time in total.
Accept who you are :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 193 Graph Coloring

Post by brianfry713 » Tue Apr 01, 2014 9:33 pm

Post your full code
Check input and AC output for thousands of problems on uDebug!

dhruba07
New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

Re: 193 Graph Coloring

Post by dhruba07 » Thu Apr 03, 2014 12:09 am

AC :)
Last edited by dhruba07 on Fri Apr 04, 2014 6:21 am, edited 1 time in total.
Accept who you are :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 193 Graph Coloring

Post by brianfry713 » Fri Apr 04, 2014 12:08 am

That is AC code
Check input and AC output for thousands of problems on uDebug!

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 193 Graph Coloring

Post by prashantharshi » Mon Jun 02, 2014 6:19 am

i used bcktracking algorithm but i m getting PE..presentation error
http://ideone.com/Yf5DLo
need help

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 193 Graph Coloring

Post by prashantharshi » Mon Jun 02, 2014 6:20 am

AC :lol:

jporcelli1120
New poster
Posts: 11
Joined: Mon Jan 26, 2015 2:05 pm

Re: 193 - Graph Coloring

Post by jporcelli1120 » Thu Feb 19, 2015 7:33 pm

Anybody can help me with counter example, or insight as to why WA? I dont want the answer, just direction. Thanks guys.

Code: Select all

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

#define PI acos(-1)
#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (int)(c).size()
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPD(i, a, b) for (int i = int(a); i >= int(b); i--)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef map<int,int> mii;
typedef set<int> si;

vi B;
const int MAXN=100;
bool G[MAXN+1][MAXN+1]={{false}};

#define PROD //clocking off
int main() {
#ifndef PROD
clock_t stop_s,start_s;
start_s=clock();
#endif

	ll k, n, m; 
	cin >> k;
	while(k--) {
		cin >> n >> m;

		REP(i, 0, MAXN) { REP(j,0,MAXN) { G[i][j]=false; } }
		B.clear();

		int u, v;
		REP(i, 1, m) { cin >> u >> v; G[u][v]=true; G[v][u]=true; }

		ll r= 1 << (n+1);
		bool adj=false;
		vi s;
		REP(i, 0, r) {
			if(__builtin_popcount(i) > SIZE(B)) { REP(j, 1, n) { if(i & (1<<j)) { s.PB(j); } } }
			else { continue; }
			
			REP(j, 0, SIZE(s)-1) { 
				REP(t, j+1, SIZE(s)-1) { if(G[s[j]][s[t]]) { adj=true; break; } } 
				if(adj) { break; }
			}

			if(!adj && SIZE(s) > SIZE(B)) { B=s; }
			s.clear();
			adj=false;
		}

		cout << SIZE(B) << endl;
		REP(i, 0, SIZE(B)-1) { if(i > 0) { cout << " " << B[i]; } else { cout << B[i]; } }
		if(k > 0) { cout << endl; }
	}


#ifndef PROD
stop_s=clock();
cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
#endif
	return 0;
}
Last edited by jporcelli1120 on Thu Feb 19, 2015 10:40 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 193 - Graph Coloring

Post by brianfry713 » Thu Feb 19, 2015 10:15 pm

You can solve this using backtracking.
Check input and AC output for thousands of problems on uDebug!

jporcelli1120
New poster
Posts: 11
Joined: Mon Jan 26, 2015 2:05 pm

Re: 193 - Graph Coloring

Post by jporcelli1120 » Thu Feb 19, 2015 10:22 pm

backtrack = complete search, thats what I am doing already. I have correct answer for every input i have found so far.

UPDATE- I think i see the problem, the method of generating all subsets doesnt work for n > 64

jporcelli1120
New poster
Posts: 11
Joined: Mon Jan 26, 2015 2:05 pm

Re: 193 - Graph Coloring

Post by jporcelli1120 » Fri Feb 20, 2015 2:10 am

This is my new complete search method but now I am getting TLE even though I thought my pruning would be sufficient

Code: Select all

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

#define PI acos(-1)
#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (int)(c).size()
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPD(i, a, b) for (int i = int(a); i >= int(b); i--)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef map<int,int> mii;
typedef set<int> si;

vi B;
const int MAXN=100;
bool G[MAXN+1][MAXN+1]={{false}}, poss[2]={false, true}, cur[MAXN+1]={false};
int n, m, k;

void check() {
	vi s;
	REP(i, 1, n) { if(cur[i]) { s.PB(i); } }

	if(SIZE(s)<SIZE(B)) { return; }

	REP(j, 0, SIZE(s)-1) { 
		REP(t, j+1, SIZE(s)-1) { if(G[s[j]][s[t]]) { return; } } 
	}

	if(SIZE(s) > SIZE(B)) { B=s; }
}

void solve(int l, int c) {
	if(l>n) { check(); return; }
	else if((n-l)+c <= SIZE(B)) { return; }
	REP(i, 0, 1) {
		cur[l]=poss[i];
		solve(l+1, poss[i]?c+1:c);
	}
}

//#define PROD //clocking off
int main() {
#ifndef PROD
clock_t stop_s,start_s;
start_s=clock();
#endif

	cin >> k;
	while(k--) {
		cin >> n >> m;

		REP(i, 0, MAXN) { memset(G[i], false, (MAXN+1) * sizeof(bool)); }
		memset(cur, false, (MAXN+1) * sizeof(bool));
		B.clear();

		int u, v;
		REP(i, 1, m) { 
			cin >> u >> v; 
			G[u][v]=true; G[v][u]=true; 
		}

		solve(1, 0);

		cout << SIZE(B) << endl;
		REP(i, 0, SIZE(B)-1) { if(i > 0) { cout << " " << B[i]; } else { cout << B[i]; } }
		if(k > 0) { cout << endl; }
	}


#ifndef PROD
stop_s=clock();
cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
#endif
	return 0;
}

jporcelli1120
New poster
Posts: 11
Joined: Mon Jan 26, 2015 2:05 pm

Re: 193 - Graph Coloring

Post by jporcelli1120 » Fri Feb 20, 2015 4:03 am

pruning tips anybody, please?? :)

Post Reply

Return to “Volume 1 (100-199)”