uva 10926 (How Many Dependencies)

Algorithm used : DFS

/*
  Name: How Many Dependencies
  Copyright: golammostaeen.wordpress.com 
  Author: Golam Mostaeen
  Date: 22/11/12 22:37
  Description: Simple DFS...
*/


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

#define MAX 105

int adj[MAX][MAX];
void init(int N){
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++)adj[i][j] = 0;
  }
}

int nodeColor[MAX];

void DFS_VISIT(int source, int N){
     nodeColor=1;
  for(int i=1;i<=N;i++){
   if(nodeColor[i]==0&&i!=source&&adj[i]==1)DFS_VISIT(i,N);
  }
  nodeColor = 2;
}

int DFS(int source, int N){
  for(int i=1;i<=N;i++)nodeColor[i] = 0;
  
  for(int i=1;i<=N;i++){
   if(i!=source && adj[i]==1&&nodeColor[i]==0)DFS_VISIT(i,N);
  }
  int counter = 0;
  
  for(int i=1;i<=N;i++)if(nodeColor[i]==2)counter++;
  
  return counter;
}


int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    
    
    int N;
    while(scanf("%d",&N)==1 && N!=0){
      init(N);
      for(int i=1;i<=N;i++){
       int m;cin>>m;
       for(int j=1;j<=m;j++){
        int h;cin>>h;adj[i][h]=1;
       }
      }
      int maxD = -1;
      int ID = 0;
      for(int i=1;i<=N;i++){
       int hold=DFS(i,N);
       if(hold>maxD){
         maxD = hold;
         ID = i;
         
       }
      } 
      cout<<ID<<endl;       
    }
  return 0;
}

uva 10004 (Bicoloring)

Algorithm used : DFS

#include <iostream>
#include <cstdio>
using namespace std;

#define MAX 500

int isPreviouslyVisited[MAX];
int parent[MAX]= {-1};
int adj[MAX][MAX];

int step = 1;
int color[MAX];

void initAdj(int noOfNodes){
  for(int i=0;i<noOfNodes;i++){
     for(int j=0;j<noOfNodes;j++){
	   adj[i][j] = 0;
	 }

  }
}

void loadAdj(int noOfEdges){

 for(int i=1;i<=noOfEdges;i++){
     int node1,node2;
	 scanf("%d %d",&node1,&node2);
     adj[node1][node2] = adj[node2][node1] = 1;
 }
}

void initAllProperties(int noOfNodes){
	for(int i=0;i<noOfNodes;i++){
	 parent[i] = -1;
	 isPreviouslyVisited[i] = 0;
	 color[i] = -1;
	}
}

void dfsVisit(int theNode,int noOfNodes,int colorWith){
	
 for(int i=0;i<noOfNodes;i++){
	 if(i!=theNode && adj[theNode][i]==1&&isPreviouslyVisited[i]==0){
		 
	 
		  isPreviouslyVisited[i] = 1;
		  color[i] = colorWith%2;
		  dfsVisit(i,noOfNodes,colorWith+1);
		 
	  

  }
 }


}

void dfs(int noOfNodes){
  initAllProperties(noOfNodes);
  
  
  for(int i=0;i<noOfNodes;i++){
	  
	  if(isPreviouslyVisited[i]==0){
		  isPreviouslyVisited[i] = 1;
		 
		  color[i] = 1;
		  
		  dfsVisit(i,noOfNodes,2);
	  }
  }

}

bool isBiocolorable(int noOfNodes){
	
    bool flag = true;
	for(int i=0;i<noOfNodes;i++){
	   for(int j=0;j<noOfNodes;j++){
	      if(adj[i][j]==1&&color[i]==color[j]){
			  
		    flag = false;
			break;
		  }
	   }
	   if(flag==false)break;
	}

	return flag;
}
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	int noOfNodes;

	while(scanf("%d",&noOfNodes)==1&&noOfNodes!=0){
	 int noOfEdges;
	 scanf("%d",&noOfEdges);
	 initAdj(noOfNodes);
	 loadAdj(noOfEdges);
	 dfs(noOfNodes);

	 bool bicolorabe = isBiocolorable(noOfNodes);

	if(bicolorabe==true)printf("BICOLORABLE.\n");
	 else printf("NOT BICOLORABLE.\n");

	 
	}



	return 0;
}