題目鏈接
problem
給出一個\(n\)個點\(m\)條邊的無向圖，然后有\(Q\)次詢問，每次詢問會給出\(k\)條邊，你需要回答刪掉這\(k\)條邊之后這個無向圖還是不是連通，
\(n\le 10^5,m\le 5\times 10^5,k\le 15\)
solution
先找出一個\(dfs\)樹，考慮在什么情況下無向圖會變得不連通，
當且僅當存在一條樹邊，滿足所有覆寫這條樹邊的返祖邊和這條樹邊都被洗掉時，無向圖不連通，
那么如何判斷是不是存在這樣一條樹邊呢，我們可以給每條返祖邊隨機一個權值，每條樹邊的權值就是所有覆寫它的返祖邊的權值異或和，對于一次查詢，如果查詢的邊權線性相關說明一定能找到一個子集異或和為0，也就是滿足無向圖不連通的條件了，
code
/*
* @Author: wxyww
* @Date: 2020-05-25 16:14:15
* @Last Modified time: 2020-05-25 16:47:10
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 500100;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
int n,m;
struct node {
int v,nxt,w,id;
}e[N << 1];
int head[N],ejs = 1;
void add(int u,int v,int id) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].id = id;
}
int vis[N],w[N];
void dfs1(int u,int fa) {
vis[u] = 1;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(e[i].w || v == fa) continue;
if(vis[v]) {
e[i].w = e[i ^ 1].w = rand() + 1;
w[u] ^= e[i].w;w[v] ^= e[i].w;
continue;
}
dfs1(v,u);
}
}
void dfs2(int u,int fa) {
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;if(v == fa || e[i].w) continue;
dfs2(v,u);
w[u] ^= w[v];
e[i].w = e[i ^ 1].w = w[v];
}
}
int cnt,p[32];
int ins(int x) {
// printf("!!!%d\n",x);
for(int i = 30;i >= 0;--i) {
if(x >> i & 1) {
if(!p[i]) {p[i] = x;return 1;}
x ^= p[i];
}
}
return 0;
}
void solve() {
int k = read(),flag = 0;
for(int i = 1;i <= k;++i) {
int x = read() ^ cnt;
// printf("%d ",x);
if(flag) continue;
if(!ins(e[x << 1].w)) {
puts("Disconnected");
flag = 1;
continue;
}
}
// puts("");
if(!flag) {
++cnt;
puts("Connected");
}
}
int main() {
// freopen("1.in","r",stdin);
n = read(),m = read();
for(int i = 1;i <= m;++i) {
int u = read(),v = read();
add(u,v,i);add(v,u,i);
}
dfs1(1,0);
dfs2(1,0);
int Q = read();
while(Q--) {
memset(p,0,sizeof(p));
solve();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/24320.html
標籤：C++