T67747 边的分类 （图上dfs）

T67747 边的分类
提交
20
通过
15
时间限制
1.00s
内存限制
62.50MB
提交答案
加入收藏
题目提供者
BDFZ-OIER
难度
暂无评定
历史分数
100
提交记录
标签
暂无标签
进入讨论版
相关讨论
暂无
推荐题目
暂无
展开
题目描述
给定无权有向图G(V,E)，dfs确定每条边的种类。当边(u, v)第一次被遍历,

考虑v的颜色

1.白色，(u,v)为T边，包含在dfs树中

2.灰色，(u,v)为B边，dfs树中子孙指向自己直系祖先的一条边

3.黑色: (u,v)为F边或C边. 此时需要进一步判断

3.1. 若prev[u] < prev[v]：u是v的直系祖先，F边

3.2. 若prev[u] > prev[v]：v早就被发现了, C边

输入格式
第一行包含两个整数N、M，表示该图共有N个结点和M条有向边。（N <= 5000，M <= 200000） 接下来M行，每行包含2个整数{u,v}，表示有一条有向边 u指向v

输入顺序保证是字典序
输出格式
M行，依照输入顺序，每行输出边的u、v、种类

输入输出样例
输入 #1复制
5 9
1 2
1 3
1 4
2 3
3 4
3 5
5 1
5 2
5 4
输出 #1复制
1 2 T
1 3 F
1 4 F
2 3 T
3 4 T
3 5 T
5 1 B
5 2 B
5 4 C
说明/提示
for(int i=1;i<=N;i++)
{
if(prev[i]==-1) dfs(i);
}

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
struct  node{int u,w;node(int u,int v):u(u),w(v){}
};int n,m,a,b,c;
const int maxn=5005;
vector<node>adj[maxn];
int post[maxn],pre[maxn],vis[maxn];
int t;
template<class T>
void read(T &x){ll f=1;x=0;char c=getchar();while(!isdigit(c)){f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-48;c=getchar();}x*=f;
}
template<class T>
void write(T x){if(x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');
}
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
void dfs(int u){pre[u]=++t;for(int i=0;i<adj[u].size();i++){int v=adj[u][i].u;if(pre[v]==-1){adj[u][i].w=1;}else if(post[v]==-1)adj[u][i].w=2;else {if(pre[u]>pre[v]){adj[u][i].w=4;}else if(pre[u]<pre[v]){adj[u][i].w=3;}}if(!vis[v]){vis[v]=1;dfs(v);}}post[u]=++t;
}
int main()
{  read(n);read(m);for(int i=0;i<m;i++){read(a);read(b);adj[a].push_back(node(b,0));}memset(pre,-1,sizeof(pre));memset(post,-1,sizeof(post));for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=1;dfs(i);}}for(int i=1;i<=n;i++){for(int j=0;j<adj[i].size();j++){switch(adj[i][j].w){case 1: printf("%d %d T\n",i,adj[i][j].u);break;case 2: printf("%d %d B\n",i,adj[i][j].u);break;case 3: printf("%d %d F\n",i,adj[i][j].u);break;case 4: printf("%d %d C\n",i,adj[i][j].u);break;}}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！