| 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第二种解法，用并查集加hash表，这里是1000个点，所以可以用hash表，我想要是再大一点就不适用了，用并查集，确实，可以实现，快速查询#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; }
?
两点是否连通，但是如果，删除的话，无疑也是要重建并查集，这点，就很费时间了，看源码
?
#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; }
?