map转string WebStorm Hadoop 国外镜像 java开发环境变量 acm unity3d plot iframe ssh view vue绑定class vue例子 jq遍历 rxjava线程切换 solidworks图库 hadoop组件 mysql获取当前时间戳 html下拉框默认选中 mysql将时间戳转换成日期 python中count python运算符优先级 python定义一个变量 java日期 java最新框架 java读取文件内容 java获取时间 java中map java中long php整站源码 exescope教程 苹果剪辑 ae脚本管理器 spoonwep dep dll之家 php购物车 tomcat修改端口 苹果x银色 t470拆机
当前位置: 首页 > 学习教程  > 编程语言

E. Directing Edges(拓扑排序判断有向图是否有环+无向边变为有向边使得图依然没环)

2020/8/11 21:01:53 文章标签:

E. Directing Edges
题意: 给你一张n个点m条边的图,其中有一些边是有向边,有一些边是无向边,题目要求你对所有无向边选择一个方向,使得整个图成为有向无环图(DAG),若无法做到则输出-1。
思路: 如果给定的有向边已经形成环了,那么再怎么改无向边,都无法做到。如果有向边没有形成环,那么就可以做到。我们把有向边连接起来,无向边不连接(看做一个个孤立的点),对整张图进行拓扑排序,因为每个点只有1次入队出队的机会,所以我们可以得到每个点出队的顺序。我们把每条边按照这个顺序输出就行。(无向边迎合有向边的方向,有向边中,起点肯定比终点早出队,所以我们只要把无向边也遵从这个规则就行。)

int n;
int m;
int in[maxn];
int p[maxn];
vector<int>e[maxn];
int main()
{
    ios;
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i = 1; i<=n; i++)
            in[i] = 0,p[i] = 0,e[i].clear();
        vector<pii>ans;
        int u,v,op;
        for(int i = 1; i<=m; i++){
            cin>>op>>u>>v;
            ans.push_back(mp(u,v));
            if(op == 1){
               e[u].push_back(v);
               in[v]++;
            }
        }
        int sum = 0;
        queue<int>q;
        for(int i = 1; i<=n; i++)
        {
            if(in[i] == 0)
                q.push(i);
        }
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            sum++;
            p[u] = sum;
            for(int i = 0; i<e[u].size(); i++)
            {
                int v = e[u][i];
                in[v]--;
                if(in[v] == 0)
                    q.push(v);
            }
        }
        if(sum!=n)
            cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;
            for(int i = 0; i<ans.size(); i++)
            {
                int fi = ans[i].first;
                int se = ans[i].second;
                if(p[fi] > p[se])
                    cout<<se<<" "<<fi<<endl;
                else
                    cout<<fi<<" "<<se<<endl;
            }
        }
    }
}


本文链接: http://www.dtmao.cc/news_show_100463.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?