OJ Board

Code: Select all

1

F
AB
BC
CA
DE
EF
FD

Code: Select all

ac

Code: Select all

1

    E     
       AB         
         CE         
           DB          
          EC  

Code: Select all

1

E     
AB         
CE         
DB          
EC 

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <list>
#include <algorithm>
#define MAX 20000

using namespace std;

int numV;
queue<int> theQ;
list <int> L[MAX];
list<int>::iterator k;

int color[MAX];
void callBFS(int u);

void recolor(int n){
	for(int i = 0; i<n;i++){
		color[i] = 0;
	}
}

void flush(){
	while(!theQ.empty())
		theQ.pop();
}

int main()
{
	//freopen("in.txt","rt",stdin);
	int i,j,testCase;
	char edge[3];
	scanf("%d\n\n",&testCase);	
	for(i = 0; i < testCase; i++)
	{	
		if(i != 1)
			printf("\n");
		scanf("%c\n",&(int)numV);
		numV -= 'A'-1;

		for(j = 0; j < numV; j++){			
			L[j].clear();			
		}

		while(true){
			gets(edge);
			sscanf(edge,"%s",edge);
			if(!strcmp(edge,"\0"))
				break;
			
			L[int(edge[0] - 'A')].push_back(int(edge[1] - 'A'));
			L[int(edge[1] - 'A')].push_back(int(edge[0] - 'A'));
		}
				
		int num = 0;
		for(j = 0; j < numV; j++){						
			if(color[j] == 0){
				callBFS(j);
				num++;
			}
			
		}
		printf("%d\n",num);
		flush();
		recolor(numV);
	}		
	return 0;
}
void callBFS(int u){		
	theQ.push(u);
	color[u] = 1;
	while(!theQ.empty()){
		u = theQ.front();
		theQ.pop();					
		for(k = L[u].begin(); k != L[u].end(); ++k){
			if(color[*k] == 0){				
				theQ.push(*k);
				color[*k] = 1;
			}
		}
	}	
}

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <queue>
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

int graph[30][30];
int color[30];

void bfs(int source,int V)
{
	int i,u;
	
	queue<int>Q;
	color[source] = GRAY;	
	Q.push(source);
	while(!Q.empty())
	{
		u = Q.front();
		Q.pop();
		for(i = 0; i < V;i++)
		{
			if(graph[u][i] && color[i] == WHITE)
			{
				color[i] = GRAY;				
				Q.push(i);
			}
		}
		color[u] = BLACK;
	}
}

int main()
{
	
	
	freopen("in.txt","rt",stdin);
	char edge[100],str[5];
	int f,test,i,j,num;
	char largerNode;
	int maxNode;
	
	f = 0;
	scanf("%d\n",&test);
	while(test--)
	{
		if(f)
		{
			scanf("\n");
			printf("\n");
		}
		f = 1;
		scanf("%c\n",&largerNode);
		maxNode = largerNode - 64;
		for(i = 0; i < maxNode;i++)
			for(j = 0; j < maxNode; j++)
				graph[i][j] = 0;
			
		while(gets(edge))
		{
			if(!strcmp(edge,"\n") || !strcmp(edge,"\0") || !strcmp(edge," "))
				break;
			j = 0;
			for(i = 0; edge[i];i++)
			{
				if(isupper(edge[i]))
					str[j++] = edge[i];
			}
			edge[j] = NULL;
			int u = str[0] - 'A';
			int v = str[1] - 'A';
			graph[u][v] = 1;
			graph[v][u] = 1;
		}
		
		for(i = 0; i < maxNode;i++)
			color[i] = WHITE;
		num = 0;
		for(i = 0; i < maxNode; i++)
		{
				
			if(color[i] == WHITE)
			{
				bfs(i,maxNode);
				num++;
			}
				
		}
		printf("%d\n",num);
	}
	return 0;
}

Code: Select all

Removed After AC.

Code: Select all

2

A

C
AB

Code: Select all

1

2

Code: Select all

char str[10000],max,*p,tmp[10];
   scanf("%d",&test);
   gets(str);
   gets(str);
   for(int i = 0; i < test; i++){      
      
	   
      if(i )
         printf("\n");
      scanf("%s",&tmp);
	  max=tmp[0];
      nV = max - 64;
	  gets(str);

Code: Select all

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define MAX 26
int adj[MAX][MAX];
int color[MAX];
int maximum;

void init(void)
{
	int i,j;
	for(i=0;i<MAX;i++)
	{
		color[i] = 0;
		for(j=0;j<MAX;j++)
			adj[i][j] = 0;
	}
	return ;
}

void bfs(int start)
{
	int u;
	queue<int>Q;
	color[start] = 1;
	Q.push(start);
	while(!Q.empty())
	{
		u = Q.front();
		for(int i=0;i<=maximum;i++)
			if(adj[u][i] && !color[i])
			{
				Q.push(i);
				color[i] = 1;
			}
		Q.pop();
		color[u] = 2;
	}
	return ;
}

main()
{
	int test,i,total;
	char ch;
	char str[10];
	cin>>test;
	int flag = 1;
	while(test--)
	{
		scanf(" %c ",&ch);
		maximum = ch - 'A';
		init();
		while(gets(str))
		{
			if(!strcmp(str,"\n") || !strcmp(str,"\0") || !strcmp(str," "))
				break;
			adj[str[0]-'A'][str[1]-'A'] = adj[str[1]-'A'][str[0]-'A'] = 1;
		}
		for(i=0,total=0;i<maximum;i++)
			if(!color[i])
			{
				bfs(i);
				total++;
			}
		if(flag)
			cout<<total<<endl;
		else
			cout<<endl<<total<<endl;
		flag = 0;
	}
	return 0;
}

Code: Select all

Cut.....................