[POI2008]CLO-Toll

题意描述

Byteotia城市有n个 towns m条双向roads. 每条 road 连接两个不同的 towns ,没有重复的road. 你要把其中一些road变成单向边使得：每个town都有且只有一个入度

题解：

这道题是并查集的一种应用。

我们在大脑中开始想象。

所有点入度都为1是一种什么样子的图呢？

树。

对，对于图论的题，我们先想一想它有没有可能是特殊图，具体一点说，是树状图。

所以我们想到，如果是一棵从根节点层层向下指向的树，我们能百分百保证这棵树上的所有点的入度为1.

如果你点头了，说明你错的很惨。

因为根节点的入度为0.

所以我们再想一想，什么样的图能使得树的根节点的入度不为0而为1？

基环树。

我们分析一下，什么时候能使得这张图无论如何也不能出现题目所说的情况？

假如一个连通块中不存在环，就绝对不会使得每个点都有1个入度。

所以我们开始想判环。

于是我们想到了并查集。

每条边链接的两个点，如果这两个点属于不同的块，就可以将其合并，并在其祖先上打标记。

如果两个祖先有一个倍打过标记，那整个的就都可以打标记，

所以AC本题：

#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

int fa[100001];

int v[100001];

int find(int x)

{

    return x==fa[x]?x:fa[x]=find(fa[x]);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

        fa[i]=i;

    for(int i=1;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        int fx=find(x);

        int fy=find(y);

        if(fx!=fy)

        {

            fa[fx]=fy;

            v[fy]=(v[fx]|v[fy]);

        }

        else

            v[fx]=1;

    }

    for(int i=1;i<=n;i++)

        if(v[find(i)]==0)

        {

            printf("NIE");

            return 0;

        }

    printf("TAK");

    return 0;

}

巴特西

POI2008 CLO-Toll

[POI2008]CLO-Toll

题意描述

题解：

最新文章

热门文章