Connections Gym - 101630C 2019-10-04 算法竞赛 暂无评论 73 次阅读 题目链接：[https://codeforces.com/group/xrTA2IaQje/contest/254939](https://codeforces.com/group/xrTA2IaQje/contest/254939)  ## 题意 一个连通图有n个顶点，有m条有向边，没有重边自环，要保证在删除（m-2*n）条边的情况下，（即使边数变为2*n条 ）这个图仍然是连通的（连通表示，从图上任意一点 i 出发都能到达图上任意一点 j ），要求输出删掉的 m-2*n 条边。 ## 思路 正向建图，从1 开始dfs ，标记从1到达其他节点所经过的边；这样可以选出从1 到其他点所需的边； 反向建图，从1 开始dfs ，标记从1到达其他节点所经过的边；这样可以求出从其他点到1 所需的边； 两次dfs 标记的边能够保证图是连通的，而且边数小于2\*n, 然后删未被标记的边直到边数=2\*n. ## 代码 ```javascript #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int n,m,t; vector<pair<int,int> > v1[N],v2[N]; bool book1[N],book2[N]; void dfs1(int p) { book1[p]=1; for(int i=0;i<v1[p].size();i++) { if(!book1[v1[p][i].first]) { v1[p][i].second=1; dfs1(v1[p][i].first); } } } void dfs2(int p) { book2[p]=1; for(int i=0;i<v2[p].size();i++) { if(!book2[v2[p][i].first] ) { int lin = v2[p][i].first; for(int j=0;j<v1[lin].size();j++) { if(v1[lin][j].first == p ) v1[lin][j].second = 1; } dfs2(v2[p][i].first); } } } int main() { scanf("%d",&t); while(t--) { memset(book1,false,sizeof(book1)); memset(book2,false,sizeof(book2)); scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) {v1[i].clear();v2[i].clear();} for(int i=1; i<=m; i++) { int l,r; scanf("%d%d",&l,&r); v1[l].push_back(make_pair(r,0)); v2[r].push_back(make_pair(l,0)); } dfs1(1); dfs2(1); int cnt=0; for(int i=1; i<=n; i++) { for(int j=0; j<v1[i].size(); j++) { if(v1[i][j].second==0&&cnt<m-2*n) { printf("%d %d\n",i,v1[i][j].first); cnt++; } if(cnt>=m-2*n) break; } if(cnt>=m-2*n) break; } } } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭