Submission #2978667

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

//#define int long long 
#define put(n) cout<<(n)<<"\n"
#define FOR(i,num,N) for(int(i)=(num);(i)<(N);(i)++)
#define RFOR(i,num,N) for(int (i)=(num);(i)>(N);(i)--)
#define all(v) (v).begin() , (v).end()
#define rall(v) (v).rbegin() , (v).rend()

int N,M;
vector<pair<int,int>> U_V;
vector<bool> reached;
int ans = 0;
bool closed;

void dfs(int node){
    reached[node] = true;//到達した
    FOR(i,0,M){
        if(U_V[i].first == node){//頂点と同じU[i]を探す
            if(!reached[U_V[i].second]){//V[i]に辿りついていないなら潜る
                dfs(U_V[i].second);
            }
            else closed = true;//連結成分に閉路があればフラグを立てる
        }
    }
}

signed main(){
   //閉路を含まないグラフ ->閉路を探す ->DFS?(全部辿れそう)->どうやって閉路を探す?
   //閉路にはループがあるからそれを使えはよさそう?
   //始点まで戻ってこれるのが閉路を持つグラフ
   //連結かどうかを調べる必要はなさそう(与えられているので)
   //木でないなら一筆書きができる
    
    cin>>N>>M;
    U_V.resize(M);
    reached.assign(N+1,false);

    FOR(i,0,M){
       cin>>U_V[i].first>>U_V[i].second;
    }

    //sort(all(U_V));

    FOR(i,1,N+1){
        if(!reached[i]){//各頂点を調べて、まだたどり着いていないなら
            closed = false;
            ++ans;//連結成分をカウント
            dfs(i);//頂点を始点に潜る
            if(closed) --ans;//連結成分に閉路があればカウントしない
        }
    }
    put(ans);
}

/*
5 6
1 2
1 3
1 4
1 5
2 3
4 5
*/

Submission Info

Judge Result