常州Day1

图的联通性问题

接触了Tarjan算法，还是可以理解的，只不过代码实现还是比较吃力
完成了p1656炸铁路

#include <bits/stdc++.h>
using namespace std;
bool s[155][155];//简单易懂的邻接矩阵^O^
struct Edge {
    int x,y;
} E[5005];
int dfn[155],low[155],n,m,id,cnt,f[155];
bool cmp(struct Edge a,struct Edge b) {
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
void addEdge(int x,int y) {
    E[++cnt].x=x;//误写成cnt++调了好久qwq
    E[cnt].y=y;
}
void tarjan(int x) {
    int y;
    dfn[x]=low[x]=++id;
    for(int i=1; i<=n; i++) {
        if(!s[x][i])continue;
        y=i;
        if(dfn[y]&&y!=f[x])low[x]=min(low[x],dfn[y]);
        if(!dfn[y]) {
            f[y]=x;
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])addEdge(x,y);
        }
    }
}
int main() {
    int x,y;
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>x>>y;
        s[x][y]=s[y][x]=1;
    }
    for(int i=1; i<=n; i++) {
        if(!dfn[i])tarjan(i);
    }
    sort(E+1,E+cnt+1,cmp);
    for(int i=1; i<=cnt; i++) {
        cout<<min(E[i].x,E[i].y)<<&#039; &#039;<<max(E[i].x,E[i].y)<<endl;
    }
    return 0;
}