程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2838 Graph Connectivity

poj2838 Graph Connectivity

編輯:C++入門知識

poj2838 Graph Connectivity


Graph Connectivity Time Limit: 8000MS   Memory Limit: 131072K Total Submissions: 3381   Accepted: 883 Case Time Limit: 3000MS

Description

Let us consider an undirected graph G = < V, E >. At first there is no edge in the graph. You are to write a program to calculate the connectivity of two different vertices. Your program should maintain the functions inserting or deleting an edge.

Input

The first line of the input contains an integer numbers N (2 <= N <= 1000) -- the number of vertices in G. The second line contains the number of commands Q (1 <= Q <= 20000). Then the following Q lines describe each command, and there are three kinds of commands:

I u v: Insert an edge (u, v). And we guarantee that there is no edge between nodes u and v, when you face this command.
D u v: Delete an existed edge (u, v). And we guarantee that there is an edge between nodes u and v, when you face this command.
Q u v: A querying command to ask the connectivity between nodes u and v.

You should notice that the nodes are numbered from 1 to N.

Output

Output one line for each querying command. Print "Y" if two vertices are connected or print "N" otherwise.

Sample Input

3 
7
Q 1 2
I 1 2
I 2 3
Q 1 3
D 1 2
Q 1 3
Q 1 1

Sample Output

N
Y
N

Y

題意是,給定點數,給出無向邊,可以動態的增加刪除查詢兩點是否連通

第一種解法

這裡很容易想到圖,創建一個鄰接表,查詢直接用bfs即可,當然dfs也是差不多的,這裡給出bfs查詢,鄰接表,就用vector算了,可以偷偷懶!

 

#include "stdio.h"
#include "string.h"
#include "math.h"
#include 
#include 
#include 
#include 
using namespace std;
#define M 1000000
#define N 20005
vector edge[N];
bool vis[N];
queue que;
bool query(int s, int e)
{
	if (s == e)
		return true;
	memset(vis, false, sizeof(vis));
	vis[s] = true;
	while (!que.empty())
	{
		que.pop();
	}
	que.push(s);
	while (!que.empty())
	{
		int k = que.front();
		que.pop();
		vector::iterator it;
		for (it = edge[k].begin(); it != edge[k].end(); it++)
		{
			if (*it == e)
				return true;
			if (!vis[*it])
			{
				que.push(*it);
				vis[*it] = true;
			}
		}
	}
	return false;
}
void inset(int s, int e)
{
	edge[s].push_back(e);
}
void deleteedge(int s, int e)
{
	vector::iterator it;
	int i;
	for (it = edge[s].begin(), i = 0; it != edge[s].end(); it++, i++)
	{
		if (*it == e)
		{
			edge[s].erase(it);
			return;
		}
	}
}
void init()
{
	for (int i = 0; i < N; i++)
	{
		edge[i].clear();
	}
}
int main()
{
	int n, tcase;
	char q;
	int s, e;
	while (scanf("%d", &tcase) != EOF)
	{
		init();
		scanf("%d", &n);
		while (n--)
		{
			getchar();
			q = getchar();
			scanf("%d%d", &s, &e);
			//printf("%c %d %d", q, s, e);
			if (q == 'Q')
			{
				if (query(s, e))
					printf("Y\n");
				else
					printf("N\n");
			}
			else if (q == 'I')
			{
				inset(s, e);
				inset(e, s);
			}
			else if (q == 'D')
			{
				deleteedge(s, e);
				deleteedge(e, s);
			}
		}
	}
	return 0;
}
第二種解法,用並查集加hash表,這裡是1000個點,所以可以用hash表,我想要是再大一點就不適用了,用並查集,確實,可以實現,快速查詢

 

兩點是否連通,但是如果,刪除的話,無疑也是要重建並查集,這點,就很費時間了,看源碼

 

#include "stdio.h"
#include "string.h"
#include "math.h"
#include 
#include 
using namespace std;
#define N 1005
#define M 20005
bool edge[N][N];
int father[N];
void initFather();
int insertFather(int s, int e);
int findfather(int s);
int ncount;
struct node {
	int s, e;
};
node queue[M];
int sum = 0;
void createFather()
{
	initFather();
	for (int i = 0; i < sum;i++)
	{
		if (edge[queue[i].s][queue[i].e])
			insertFather(queue[i].s, queue[i].e);
	}
}
void initFather()
{
	for (int i = 0; i <= ncount; i++)
	{
		father[i] = i;
	}
}
int insertFather(int s, int e)
{
	int x = findfather(s);
	int y = findfather(e);
	if ( x != y)
		father[x] = findfather(y);
	return 0;
}
int findfather(int s)
{
	if (father[s] == s)
		return s;
	else
		return father[s] = findfather(father[s]);
}
bool query(int s, int e)
{
	if (findfather(s) == findfather(e))
		return true;
	else 
		return false;
}
void deleteedge(int s, int e)
{
	edge[s][e] = false;
}
void init()
{
	memset(edge, false, sizeof(edge));
	sum = 0;
	createFather();
}
int main()
{
	int n,tcase;
	char q;
	int s, e;
	while (scanf_s("%d", &tcase) != EOF){
		//while (tcase--)
		{
			ncount = tcase;
			init();
			scanf_s("%d", &n);
			
			while (n--)
			{
				getchar();
				q = getchar();
				scanf_s("%d%d", &s, &e);
				//printf("%c %d %d", q, s, e);
				if (q == 'Q')
				{
					if (query(s, e))
						printf("Y\n");
					else
						printf("N\n");
				}
				else if (q == 'I')
				{
					edge[s][e] = true;
					edge[e][s] = true;
					queue[sum].s = s;
					queue[sum].e = e;
					sum++;
					insertFather(s, e);
				}
				else if (q == 'D')
				{
					deleteedge(s, e);
					deleteedge(e, s);
					createFather();
				}
			}
		}
	}
	return 0;
}


第三種 方法 鄰接表加上並查集,這樣比上面兩種方法,省了時間,也省了內存

 

 

#include "stdio.h"
#include "string.h"
#include "math.h"
#include 
#include 
#include 
#include 
using namespace std;
#define N 1005
#define SCANF scanf
vector edge[N];
int ncount;
queue que;
int father[N];
void initFather();
int insertFather(int s, int e);
int findfather(int s);
void createFather()
{
	initFather();
	int i = 0;
	vector::iterator it;
	for (int s = 0; s <= ncount; s++)
	{
		for (it = edge[s].begin(), i = 0; it != edge[s].end(); it++, i++)
		{
			insertFather(s, *it);
		}
	}
}
void initFather()
{
	for (int i = 0; i <= ncount; i++)
	{
		father[i] = i;
	}
}
int insertFather(int s, int e)
{
	int x = findfather(s);
	int y = findfather(e);
	if (x != y)
		father[x] = findfather(y);
	return 0;
}
int findfather(int s)
{
	if (father[s] == s)
		return s;
	else
		return father[s] = findfather(father[s]);
}
bool query(int s, int e)
{
	if (findfather(s) == findfather(e))
		return true;
	else
		return false;
}
void inset(int s, int e)
{
	edge[s].push_back(e);
	insertFather(s, e);
}
void deleteedge(int s, int e)
{
	vector::iterator it;
	int i;
	for (it = edge[s].begin(), i = 0; it != edge[s].end(); it++, i++)
	{
		if (*it == e)
		{
			edge[s].erase(it);
			return;
		}
	}
}
void init()
{
	for (int i = 0; i <= ncount; i++)
	{
		edge[i].clear();
	}
	createFather();
}
int main()
{
	int n, tcase;
	char q;
	int s, e;
	while (SCANF("%d", &tcase) != EOF)
	{
		ncount = tcase;
		init();
		SCANF("%d", &n);
		while (n--)
		{
			getchar();
			q = getchar();
			SCANF("%d%d", &s, &e);
			//printf("%c %d %d", q, s, e);
			if (q == 'Q')
			{
				if (query(s, e))
					printf("Y\n");
				else
					printf("N\n");
			}
			else if (q == 'I')
			{
				inset(s, e);
				inset(e, s);
			}
			else if (q == 'D')
			{
				deleteedge(s, e);
				deleteedge(e, s);
				createFather();
			}
		}
	}
	return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved