1. 首页
2. 连通图
3. 本页

Codeforces 131D Subway (缩点)

题意：~

思路：缩点之后求个最短路

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
#define pb push_back
#define Key_value ch[ch[root][1]][0]
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
const double eps = 1e-8;
const double pi = acos (-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int M = 1000100;
const int MAXN = 3010;
const int MAXM = 10050;

struct Edge
{
    int to, next;
} edge[MAXM];
int head[MAXN], tot;
int Low[MAXN], DFN[MAXN], Stack[MAXN], Belong[MAXN];
int Index, top;
int scc;

bool Instack[MAXN];
int num[MAXN];

void addedge(int u, int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void Tarjan(int u, int fa)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if(v == fa) continue;
        if( !DFN[v] )
        {
            Tarjan(v, u);
            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 = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc;
            num[scc]++;
        }
        while( v != u);
    }
}
void solve(int N)
{
    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, 0);
}
void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
}

struct mmp
{
    int v, cost;
    mmp(int _v = 0, int _cost = 0): v(_v), cost(_cost) {}
};
vector<mmp>E[MAXN];

void adds(int u, int v, int w)
{
    E[u].pb(mmp(v, w));
}
bool vis[MAXN];
int dist[MAXN];

void gg(int start, int n)
{
    MS(vis, false);
    fill(dist, dist + n + 1, INF);
    vis[start] = 1;
    dist[start] = 0;
    queue<int >que;
    while(!que.empty())que.pop();
    que.push(start);
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for(auto &i : E[u])
        {
            int v = i.v;
            if(dist[v] > dist[u] + i.cost)
            {
                dist[v] = dist[u] + i.cost;
                if(!vis[v])
                {
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

int du[3050];

int main()
{
    int n;
    cin >> n;
    init();
    int u, v;
    for(int i = 0; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    solve(n);
    int st;
    for(int i = 1; i <= n; ++i)
    {
        du[Belong[i]]++;
        if(du[Belong[i]] > 1)
        {
            st = Belong[i];
            break;
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = head[i]; ~j; j = edge[j].next)
        {
            if(Belong[edge[j].to] != Belong[i])
                adds(Belong[i], Belong[edge[j].to], 1);
        }
    }
    gg(st, n);
    for(int i = 1; i <= n; ++i) cout << dist[Belong[i]] << (i == n ? "\n" : " ");
    return 0;
}