Gym - 101630 C - Connections 两次dfs强连通图

codeforces的链接：Gym - 101630 C - Connections 牛客的链接：https://ac.nowcoder.com/acm/problem/54385

题目描述

输入描述

输出描述

样例

题意

一个有向图，有n个点，有m条边，现在需要你删除m-2n条边，使得剩下的2n条边依旧可以组成强连通图，且把删除的边输出

题解

正反向建图且对各个边进行相同的下标标记，默认1为起始位置，分别在正反图进行dfs遍历，并判断是否经历过该点和该边，这就可以保证有一个强连通图了，故可以直接for遍历选出前n-2*m个没有被遍历过的边了。

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" const int MAX=1e6+7; const int mod=1e9+7; const int inf=0x3f3f3f3f; struct node{ int to,id; }; bool vis[MAX],check[MAX]; vector<pair<int,int>>edge; vector<node>g[MAX],g2[MAX]; void dfs1(int u){ vis[u]=1; for(auto it: g[u]){ int v=it.to, id=it.id; if(!vis[v]){ check[id]=1; dfs1(v); } } } void dfs2(int u){ vis[u]=1; for(auto it:g2[u]){ int v=it.to,id=it.id; if(!vis[v]){ check[id]=1; dfs2(v); } } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0); int t;cin>>t; while(t--){ int n,m;cin>>n>>m; edge.clear(); for(int i=0;i<=m;i++)vis[i]=check[i]=0; for(int i=0;i<=n;i++)g[i].clear(),g2[i].clear(); for(int i=0;i<m;i++){ int u,v;cin>>u>>v; g[u].push_back({v,i}); g2[v].push_back({u,i}); edge.push_back({u,v}); } dfs1(1); for(int i=0;i<=m;i++)vis[i]=0; //反向边遍历需清0 dfs2(1); for(int i=0,j=0;i<m&&j<m-2*n;i++){ if(!check[i]){ j++; cout<<edge[i].first<<" "<<edge[i].second<<endl; } } } return 0; }