【NOIP2015四校联训Day7】题题解（Tarjan缩点+DFS）

前言：没错，这题的名字就这么直白。我们考试题。

------------------

你需要完成$n$道题目。有一些题目是相关的，当你做一道题的时候，如果你做过之前对它有帮助的题目，你会更容易地做出它。当然，如果题目$x$对题目$y$有帮助，题目$y$并不一定对题目$x$有帮助。你可以自由安排做题顺序。现在，你想要知道，你在完成所有题目的情况下，可能有多少题目是在有帮助的情况下完成的。

请注意：帮助具有传递性，即$a$对$b$有帮助，$b$对$c$有帮助，那么$a$对$c$有帮助。

-----------------------------------

首先，我们考虑特殊情况。假设图是一条链。那么答案是$0-(n-1)$。

$0$：逆向走图。

$n-1$：顺向走图。

其他：“交流电”般地走。

如果图是多个连通块（多条链），答案显然是$0-k(n-1)$。

现在考虑有强连通分量的情况（一条链）。假设强连通分量的大小为$size$，那么可取的答案为$size-1$或$size$。

$size-1$表示从儿子走到父亲的情况。由于点都是互达的，所以只要到达一个点，其他点都是可达的。

$size$表示从父亲走到儿子。这时所有点都符合要求。

得到结论，答案范围为$\sum_{i=1}^k (size[i]-1)$到缩点之前点个数减缩点之后点个数。

现在考虑一般情况（一个连通块）。把它当成一条链显然会漏掉答案，因为此时图有可能是一个无根树。所以我们需要$dfs$，把这棵树分成许多链，再进行计算。

考虑有多个连通块且一般的情况，我们只需用到前面的结论然后遍历全图即可。

考虑文字比较抽象，我把自己的思路写出来。（字比较丑。大佬轻喷QAQ）

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int cnt,dfn[maxn],vis[maxn],pos[maxn],low[maxn];

int st[maxn],top,tot;

int sum[maxn],size[maxn],num[maxn];

int jishu,head[maxn];

int n,m,x[maxn],y[maxn],du[maxn],chu[maxn];

int k,res;

struct node

{

    int next,to,dis;

}edge[maxn];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void add(int from,int to)

{

    edge[++jishu].next=head[from];

    edge[jishu].to=to;

    head[from]=jishu;

}

void tarjan(int now)

{

    dfn[now]=low[now]=++cnt;

    st[++top]=now;vis[now]=;

    for (int i=head[now];i;i=edge[i].next)

    {

        int to=edge[i].to;

        if (!dfn[to]) tarjan(to),low[now]=min(low[now],low[to]);

        else if (vis[to]) low[now]=min(low[now],dfn[to]);

    }

    if (low[now]==dfn[now])

    {

        tot++;

        while(st[top+]!=now)

        {

            pos[st[top]]=tot;

            vis[st[top--]]=;

        }

    }

}

int dfs(int now)

{

    if (!chu[now])

    {

        vis[now]=;cnt++;

        return num[now];

    }

    cnt++;int ans=num[now];

    for (int i=head[now];i;i=edge[i].next)

    {

        int to=edge[i].to;

        if (vis[to]) continue;

        vis[to]=;

        ans+=dfs(to);

    }

    return ans;

}

void clear()

{

    memset(vis,,sizeof(vis));

    memset(head,,sizeof(head));

    memset(edge,,sizeof(edge));

    jishu=;cnt=;

}

int main()

{

    n=read(),m=read();

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

    {

        x[i]=read(),y[i]=read();

        add(x[i],y[i]);

    }

    for (int i=;i<=n;i++) if (!dfn[i]) tarjan(i);

    clear();

    for (int i=;i<=n;i++) num[pos[i]]++;

    for (int i=;i<=m;i++) if (pos[x[i]]!=pos[y[i]]) add(pos[x[i]],pos[y[i]]),du[pos[y[i]]]++,chu[pos[x[i]]]++;

    for (int i=;i<=tot;i++)

    {

        if (du[i]) continue;

        cnt=;k++;

        sum[k]=dfs(i);size[k]=cnt;

        res+=(sum[k]-size[k]);

    }

    //for (int i=1;i<=tot;i++) cout<<num[i]<<endl;

    for (int i=res;i<=(n-k);i++) cout<<i<<endl;

    return ;

}

巴特西

【NOIP2015四校联训Day7】题题解（Tarjan缩点+DFS）

最新文章

热门文章

巴特西

【NOIP2015四校联训Day7】 题 题解（Tarjan缩点+DFS）

最新文章

热门文章

【NOIP2015四校联训Day7】题题解（Tarjan缩点+DFS）