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: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第二種解法，用並查集加hash表，這裡是1000個點，所以可以用hash表，我想要是再大一點就不適用了，用並查集，確實，可以實現，快速查詢#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 #includeusing 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; }
