知识养成了思想,思想同时又在融化知识。这篇文章主要讲述UOJ UR#9 App管理器相关的知识，希望能为你提供帮助。
题目传送门
题目大意大概就是给你一个混合图(既有有向边又有无向边)，对于每条无向边，u-v，问删去u->
v，或删去v->
u那条可以使新图强连通。（保证数据有解）。
这道题前几个数据点送分。
枚举每一条边，先将它去掉，遍历图，如果可以达到所有点，即强连通。
比如去掉u->
v，其实只要dfs(u)，判断是否能到达v即可。
可以直接删去，否则删另一条边，删去后因为图强连通，所以对之后的操作无影响。
【UOJ UR#9 App管理器】code：
#include < cstdio> #include < cstring> using namespace std; int read() { char c; while(c=getchar(),c< ‘0‘||c> ‘9‘); int x=c-‘0‘; while(c=getchar(),c> =‘0‘& & c< =‘9‘)x=x*10+c-‘0‘; return x; }const int MAXN=5005; int N,M,ide[MAXN< < 1],vis[MAXN]; int head[MAXN],to[MAXN< < 1],nxt[MAXN< < 1],cnt; struct node{ int x,y,o,d; }edge[MAXN]; void add(int x,int y) { to[cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; cnt++; }void dfs(int now) { vis[now]=1; for(int i=head[now]; i!=-1; i=nxt[i]){ if(!ide[i]& & !vis[to[i]]){ dfs(to[i]); } } }int main() { N=read(),M=read(); memset(head,-1,sizeof head); for(int i=1; i< =M; i++){ int x=read(),y=read(),o=read(); add(x,y); if(!o)add(y,x); edge[i]=(node){x,y,o,cnt-1}; } for(int i=1; i< =M; i++){ if(edge[i].o){puts("0"); continue; } memset(vis,0,sizeof vis); ide[edge[i].d]=1; dfs(edge[i].y); if(vis[edge[i].x]){ puts("0"); continue; } else{ ide[edge[i].d]=0; ide[edge[i].d-1]=1; } puts("1"); continue; } return 0; }
推荐阅读
- 基于appium快速实现H5自动化测试
- AppCan
- Android Logger日志系统
- happens-before
- 安卓 二维码
- IDEA跑代码出现Error(7,8)***App is alreadydefinedasobjectAppobject Appextends Application{
- 移动端自动化测试-Windows-Android-Appium环境搭建
- 微信运动刷步助手v9.0免费安卓微信运动刷步神器
- ()android 通知