CCF-CSP题解 201509-4 高速公路

有点忧愁。\(CSP\)也考\(Tarjan\)缩点的嘛。

原理咱也不明白，咱也不敢学，找到模板就是抄。

#include<bits/stdc++.h>

const int maxn = 10000;

const int maxm = 100000;

using namespace std;

int to[maxm + 10];

int nex[maxm + 10];

int head[maxn + 10], cnt = 0;

void addEdge(int a, int b)

{

    to[cnt] = b; nex[cnt] = head[a]; head[a] = cnt++;

}

int low[maxn + 10], dfn[maxn + 10], sta[maxn + 10], belong[maxn + 10];

int index, top;

int scc;

bool inStack[maxn + 10];

int num[maxn + 10];

void Tarjan(int u)

{

    int v;

    low[u] = dfn[u] = ++index;

    sta[top++] = u;

    inStack[u] = true;

    for (int i = head[u]; i != -1; i = nex[i])

    {

        v = to[i];

        if (!dfn[v])

        {

            Tarjan(v);

            if (low[u] > low[v])

                low[u] = low[v];

        }

        else if (inStack[v] && low[u] > dfn[v])

            low[u] = dfn[v];

    }

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

    {

        scc++;

        do

        {

            v = sta[--top];

            inStack[v] = false;

            belong[v] = scc;

            num[scc]++;

        } while (v != u);

    }

}

int main()

{

    int n, m;

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

    memset(head, -1, sizeof(head));

    for (int i = 1, a, b; i <= m; i++)

    {

        scanf("%d%d", &a, &b);

        addEdge(a, b);

    }

    memset(dfn, 0, sizeof(dfn));

    memset(inStack, false, sizeof(inStack));

    memset(num, 0, sizeof(num));

    index = scc = top = 0;

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

    {

        if (!dfn[i])

            Tarjan(i);

    }

    int ans = 0;

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

    {

        ans += num[i] * (num[i] - 1) / 2;

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

CCF-CSP题解 201509-4 高速公路

最新文章

热门文章