P2017 Dizzy Cows G
Hehe_0
2021-03-27 16:25:36
### [传送门](https://www.luogu.com.cn/problem/P2017)
[USACO09DEC]Dizzy Cows G
###### ~~bike曾说过:‘我们要熟练运用STL’~~
看到这个有向边无向边,和无环,很容易想到拓扑排序。
**这题可以考虑用dfs和bfs去写**
拓扑排序,记录编号,然后无向边的顺序按排序后序号的大小确定方向
------------
## 详细看代码注释
//此处存边是用vector,可邻接表。。。
bfs策略:
如果是有向边,去记录他的入度...
将所有入度为零的点记入容器
在后面每个边的指向的入度--,当点的入度又为0时,再次入队。
这样也就可以使联通的遍历了。
```cpp
#include<bits/stdc++.h>
//bfs 版
using namespace std;
int n,p1,p2;
vector<int >a[100010];
int in[100010];//记录该点的入度
int p,w,cnt;
queue<int> q;//其实这里只是需要一个容器,stack也可(大概
int t[100001];//记录位置
int main()
{
ios::sync_with_stdio(false);
cin>>n>>p1>>p2;
for(int i=0;i<p1;i++)
{//输入有向边
cin>>p>>w;
in[w]++;//将指向的点入度++
a[p].push_back(w);//加入
}
for(int i=1;i<=n;i++)
{
if(in[i]==0)//若入度为零
q.push(i);//将其放入容器
}
while(q.size()>0)
{
int x=q.front();
q.pop();
t[x]=cnt++;//放位置
for(int i=0;i<a[x].size();i++)
{
in[a[x][i]]--;
//将此点的边指向的点的入度--
if(in[a[x][i]]==0)//若入度为零
q.push(a[x][i]);//将其入队
}
}
for(int i=0;i<p2;i++)
{
cin>>p>>w;
if(t[p]<t[w])//观察位置
cout<<p<<" "<<w<<endl;
else
cout<<w<<" "<<p<<endl;
}
return 0;
}
```
------------
dfs主要进行编号,但是以单纯以一个点无法全遍历。
注意:这样所求的序是反的。
```cpp
#include<bits/stdc++.h>
//dfs 版
using namespace std;
int n,p1,p,q,w;
vector<int >a[100011];//我们可以去用vector存边
bool v[100011];//记录是否搜过
int t[100011],cnt;
//如果 某个点想
void dfs(int x)
{
for(int i=0;i<a[x].size();i++)
{
if(!v[a[x][i]])//如果没入容器
dfs(a[x][i]);//以他为下个起点
}
v[x]=1;//标记,走过
t[x]=cnt;//编号
cnt++;
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>p1>>p2;
for(int i=0;i<p1;i++)
{
cin>>q>>w;
a[q].push_back(w);//边
}
for (int i=1;i<=n;i++)
{//多次,一次dfs很有可能走不完
if(!v[i]) //如果没走过
dfs(i);
}
for(int i=0;i<p2;i++)
{
cin>>q>>w; //因为 dfs求的是倒序
if (t[q]>t[w])//所以这里和bfs不同
cout<<q <<" "<<w<<endl;
else
cout<<w <<" "<<q<<endl;
}
return 0;
}
```
[关于拓扑排序](https://oi-wiki.org/graph/topo/)
[关于vector](https://oi-wiki.org/lang/csl/sequence-container/)
dfs求拓扑序的板子
```cpp
vector<int> G[MAXN]; // vector 实现的邻接表
int c[MAXN]; // 标志数组
vector<int> topo; // 拓扑排序后的节点
bool dfs(int u) {
c[u] = -1;
for (int v : G[u]) {
if (c[v] < 0)
return false;
else if (!c[v])
if (!dfs(v)) return false;
}
c[u] = 1;
topo.push_back(u);
return true;
}
bool toposort() {
topo.clear();
memset(c, 0, sizeof(c));
for (int u = 0; u < n; u++)
if (!c[u])
if (!dfs(u)) return false;
reverse(topo.begin(), topo.end());
return true;
}
```