DAG?

题目描述
输入一个有向图，判断该图是否是有向无环图(Directed Acyclic Graph)。

输入描述
输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=100，0<=m<=10000。
接下来的m行，每行是一个数对u v，表示存在有向边(u,v)。顶点编号从1开始。

输出描述
如果图是DAG，输出1，否则输出0

输入样例

3 3
1 2
2 3
3 1

输出样例

0

Yizuodi的答案

#include <iostream>
#include <cstring>
#include <set>
using namespace std;
const int MAX = 100001;

int main()
{
        int m, n;
        int count = 0;
        cin >> m >> n;
        multiset<int> E[MAX];
        int in_degree[MAX];                         //某个节点的入度
        memset(in_degree, 0, sizeof(in_degree)); //初始化为0
        for (int i = 1; i <= n; ++i)
        {
            int a, b;
            cin >> a >> b;    //输入一条路径
            E[a].insert(b); //
            ++in_degree[b]; //被指向的节点入度加1
        }
        set<int> q; //用于存储入度为0的节点
        for (int i = 1; i <= m; ++i)
        {
            if (in_degree[i] == 0)
            {
                ++ count;
                q.insert(i);
            }
        }
        while (!q.empty()) //拓扑排序
        {
            int temp = *q.begin();
            //cout << temp << " ";                                    //输出队列中的元素
            q.erase(temp);                                            //移出队列
            for (multiset<int>::iterator i = E[temp].begin(); i != E[temp].end(); i++) //multiset<int>::iterator
            {
                in_degree[*i]--;        //将该节点指向的节点的入度减1
                if (in_degree[*i] == 0) //如果导致指向的节点入度为0，则将节点入队列
                {
                    ++ count;
                    q.insert(*i);
                }
            }
        }
        if (count < m)
        {
            cout << "0";
        }
        else
        {
            cout << "1";
        }

}