各位大佬,能帮忙看看我的代码有什么问题吗,过了前三个测试点
  • 板块P1656 炸铁路
  • 楼主Love_lsla
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/9/13 16:37
  • 上次更新2023/11/2 21:04:31
查看原帖
各位大佬,能帮忙看看我的代码有什么问题吗,过了前三个测试点
719909
Love_lsla楼主2023/9/13 16:37
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 160,M = 5010*2;
int n,m;
int h[N],e[M],ne[M],idx;
int stk[N],top;
int dcc_cnt,id[N];
int dfn[N],low[N],timestamp;
int is_bridge[N];
vector<pair<int,int>> store;

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void tarjan(int u,int from)
{
    dfn[u] = low[u] = ++timestamp;
    stk[top++] = u;//双连通分量不需要特判在栈内
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j,i);//这里的是i,找的是来的那一条边
            low[u] = min(low[u],low[j]);
            if(dfn[u] < low[j])
                is_bridge[i] = is_bridge[i^1] = true;
        }
        else if(i != (from^1)) low[u] = min(low[u],low[j]);
    }

    if(dfn[u] == low[u])
    {
        int y;
        dcc_cnt++;
        do
        {
            y = stk[--top];
            id[y] = dcc_cnt;
        } while (u!=y);
        
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }

    tarjan(1,-1);//当前的点  上一个点
    
    int cnt = 0;
    for(int i = 0;i<idx;i+=2)
        if(is_bridge[i])
        {
            if(e[i] < e[i^1]) store.push_back({e[i],e[i^1]});
            else store.push_back({e[i^1],e[i]});
        }

    sort(store.begin(),store.end());
    store.erase(unique(store.begin(),store.end()),store.end());
    
    for(auto k : store)
    {
        cout<<k.first<<" "<<k.second<<endl;
    }
    return 0;
}
2023/9/13 16:37
加载中...