模板-判斷某有向圖是否存在拓?fù)湫蛄?/h2>

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int MAXV=1001;
int N,M;
int in[MAXV],init[MAXV];
vector<int> Adj[MAXV];

//Topo()用于判斷某有向圖是否存在拓?fù)湫蛄?bool Topo()
{
    int num=0;
    queue<int> q;
    for(int i=0; i<N; i++)
    {
        if(in[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int u=q.front();
        //printf("%d",u);//輸出拓?fù)湫蛄许旤c(diǎn)(由頭至尾),注意該函數(shù)在返回true情形下也只能產(chǎn)生唯一一個(gè)拓?fù)湫蛄?        q.pop();
        for(int i=0; i<Adj[u].size(); i++)
        {
            int v=Adj[u][i];
            in[v]--;
            if(in[v]==0)
                q.push(v);
        }
        num++;
    }
    if(num==N)
        return true;
    return false;
}
int main()
{

    cin>>N>>M;
    int u,v;
    for(int i=0; i<M; i++)
    {
        cin>>u>>v;
        Adj[u-1].push_back(v-1);//儲(chǔ)存出度頂點(diǎn)
        in[v-1]++;//統(tǒng)計(jì)入度數(shù)
    }
    if(Topo())
        cout<<"該圖存在拓?fù)湫蛄?<<endl;
    else
        cout<<"該圖不存在拓?fù)湫蛄?<<endl;
    return 0;
}
/*
輸入:
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
輸出:
該圖存在拓?fù)湫蛄?

輸入:
3 2
2 1
2 3
輸出:
該圖存在拓?fù)湫蛄?*/

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。