E. Directing Edges
题意
给出一个n个点m条边的图 n,m<2e5
m条边有一部分给定方向
确定剩下的边的方向使得最后的图不存在环
题解
用有向边建图,无向边视为两点间没有边
进行拓扑排序 每个点都有排序后的拓扑序
若最后被排序的点数<n则一定存在环输出no
否则一定可以构造出无环图
拓扑排序流程
loop：
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
若不存在入度为0的点则停止
若图中存在环, 环上的所有点入度都>=1 因此他不会被排入拓扑序中
发现对于拓扑排序的结果，对于原图中的无向边
如果将它的方向定为 顺序较后的节点 到 顺序较前的节点 的有向边，必然会构成环
因为拓扑排序本质上是点的遍历顺序, 若后遍历的点有指向先遍历的点 即返祖边 那么必然存在环
否则将无向边的方向定为先遍历的点指向后遍历的点 两者的拓扑序大小不变 不会构成返祖边
bfs实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
vector<int>mp[Max];
int in[Max],dfn[Max],u[Max],v[Max];
void bfs(){
queue<int>q;
for(int i=1;i<=n;i++)if(!in[i])q.push(i);
while(!q.empty()){
int pos=q.front();q.pop();
dfn[pos]=cnt++;
for(auto i:mp[pos]){
in[i]--;
if(in[i]==0)q.push(i);
}
}
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int mod=2e3;
const int Max=2e5+5;
int in[Max],dfn[Max],u[Max],v[Max];
int n,m,cnt=0;
bool tp[Max];
vector<int>mp[Max];
void bfs(){
queue<int>q;
for(int i=1;i<=n;i++)if(!in[i])q.push(i);
while(!q.empty()){
int pos=q.front();q.pop();
dfn[pos]=cnt++;
for(auto i:mp[pos]){
in[i]--;
if(in[i]==0)q.push(i);
}
}
}
int main(){
int t;cin>>t;
while(t--){
cin>>n>>m;cnt=0;
vector<pair<int,int> >temp;
for(int i=1;i<=n;i++){
in[i]=0,dfn[i]=0;
mp[i].clear();
}
for(int i=0;i<m;i++){
cin>>tp[i]>>u[i]>>v[i];
if(tp[i])mp[u[i]].push_back(v[i]),in[v[i]]++;
}
bfs();
if(cnt!=n)cout<<"No"<<endl;
else{
cout<<"Yes"<<endl;
for(int i=0;i<m;i++){
if(tp[i])cout<<u[i]<<" "<<v[i]<<endl;
else{
if(dfn[u[i]]<dfn[v[i]])cout<<u[i]<<" "<<v[i]<<endl;
else cout<<v[i]<<" "<<u[i]<<endl;
}
}
}
}
}
|