ABC 288 C 閉路の考え方

プログラミングも記事を書くのもガチ初心者です

閉路とは？

同じ点を2回以上通らずにたどり始めの点に帰ってくるようなたどり方が閉路
大雑把な説明しかできないので詳しくは他を参照してくれるとたすかります

ABC 288 C - Don’t be cycleで考える

[問題文]
N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1 から N の番号がついており、i 番目の辺は頂点 A[i]​ と頂点 B[i]​ を結んでいます。 このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めてください。

[制約]
・1≤N≤2×10^5
・0≤M≤2×10^5
・1≤A[i]​,B[i]​≤N
・与えられるグラフは単純
・入力はすべて整数

入力

N M
A[1] B[1]
A[2] B[2]
 :    :
A[M] B[M]

イラストで表すとこんな感じ

ここで悩んだのはどうやって閉路を発見するかで悩んだのですが閉路の特徴？的なのを知っていれば最終的にそれが閉路だったかがわかります。
あと一本辺を増やしたら閉路になる状態の辺の数は（頂点の数-1）です
よって辺で結ばれている塊ごとに頂点が何個あるのかがわかれば閉路にならないぎりぎりの本数がわかります。
上のグラフでは一つ目の塊は頂点が4個、一つ目は頂点が5個。なので辺の数は3本と4本。最初に全部の辺の数が与えられるのでそれから引けば答えがわかります。
それぞれの塊の頂点の数はDFSなどでわかります。
下のコードは塊に必要な辺の数をそのまま求めてます

DFSでの解答

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i,a,n)for (int i =(int)(a);i<=(int)(n);i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
using namespace std; 

vector<int>G[10000009];
bool vis[10000009];
int renketu=0;

void dfs(int pos){
    vis[pos]=true;
    rep(i,G[pos].size()){
      int nex=G[pos][i];
      if(vis[nex]==false){
        renketu++;
        dfs(nex);
      }
    }
}

int main(){
    int N,M;cin>>N>>M;
    rep(i,M){
      int AA,BB;cin>>AA>>BB;
      G[AA].push_back(BB);
      G[BB].push_back(AA);
    }
    rrep(i,1,N){
      if(vis[i]==false){
        dfs(i);
      }
    }
    cout<<M-renketu<<endl;
    return 0;
}

終わりに

初めて記事を書いたので分かりづらい、見づらい、求めたい情報がないなどありましたらごめんなさい。
AtCoder初心者なのでまだまだ遭遇していない問題などありますので、またこういう系の問題がでたらまた更新したいと思います。