庞各庄网站建设,视频模板网,网站设计第一步怎么做,国际进出口贸易网站题目连接
题解#xff1a;连通块问题显然要与并查集有关#xff0c;而且C4比赛极喜欢出与并查集有关的知识。
这道题可以这样做#xff0c;即我每次去掉一个城市的时候#xff0c;都对剩余的城市重新建立并查集#xff0c;然后判断联通块的数量有没有删减#xff0c;如…题目连接
题解连通块问题显然要与并查集有关而且C4比赛极喜欢出与并查集有关的知识。
这道题可以这样做即我每次去掉一个城市的时候都对剩余的城市重新建立并查集然后判断联通块的数量有没有删减如果联通块的数量没变说明没有破坏连通性而如果改变了说明破坏了连通性这样虽然很暴力时间复杂度很高但是仍然能过。。。不得不说数据很弱。
当然这道题也可以这样做由于当攻陷一个城市的时候我们需要把并查集分开但这显然是不现实的我们可以逆向思维即倒着想。先将攻打到最后剩余的城市用并查集联通起来然后倒着考虑每一个被攻打的城市把这个城市加入到城市网络里如果并查集合并次数大于1那么说明这个城市的删除会导致连通性的破坏那么发出警报。如果合并次数等于1说明该城市被攻陷不会破坏连通性因此不需要发出警报。另外需要注意输出信息需要保存在栈中在判断结束后逆序输出生成的信息。
另外我的代码第一次提交的时候只得了21分原因是把两个城市加入并查集的时候忘记 判断之间有没有道路了。。。这么严重的问题都能得21分可见数据只弱。。。
代码 #include cstdio
#include string
#include iostream
#include stack
using namespace std;
const int MAX 505;
int G[MAX][MAX];
int N,M;
int parent[MAX];
int rem[MAX];
stackint stk;
stackstring outstk;
void init()
{for(int i 0;i MAX;i) parent[i] i;
}
int find(int x)
{if(parent[x] x) return x;return parent[x] find(parent[x]);
}
bool join(int x1,int x2)
{int p1 find(x1);int p2 find(x2);if(p1 ! p2) {parent[p1] p2; return true;}return false;
}
int main()
{init();scanf(%d%d,N,M);for(int i 0;i M;i){int u,v;scanf(%d%d,u,v);G[u][v] G[v][u] 1;}int K;scanf(%d,K);if(K N) outstk.push(Game Over.\n);while(K--){int c;scanf(%d,c);rem[c] 1;stk.push(c);}for(int i 0;i N;i) if(!rem[i]) for(int j 0;j N;j) if(!rem[j] G[i][j]) join(i,j);while(!stk.empty()){int u stk.top();stk.pop();rem[u] 0;int cnt 0;for(int i 0;i N;i)if(!rem[i] G[u][i])if(join(u,i))cnt; if(cnt 2){char tmp[100];sprintf(tmp,Red Alert: City %d is lost!\n,u);outstk.push(tmp);}else{char tmp[100];sprintf(tmp,City %d is lost.\n,u);outstk.push(tmp);}}while(!outstk.empty()){coutoutstk.top();outstk.pop();}
}
