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;
}