11237: 【原1237】Courses

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1237

Description

学生需要修读完所有的课程才能毕业，这些课程之间有先导关系（比如要修读数据结构，必须先修读程序设计思想方法）。假设任意一门课程可以在任何一个学期给满足条件的学生选修，且学生每个学期可以选修的课程数不限。先给出一些课程与课程之间的关系，求能够修完所有课程的最少学期数。

为简化题目，约定：假设有n门课程，则这n门课程的编号分别为：1,2，……n。

数据保证不会出现环和自环（即总是可以合法地修完所有的课程，不会出现类似“1->1”或是“1->2->3->1”的情况）

（提示：如果你没有很好的思路，请仔细看P360开始的“拓扑排序”部分内容。）

Input Format

第1行：n m //正整数n ，代表课程的数量。非负整数m代表要给出几个先导关系。

第2行到第1+m行: a b //每行两个整数：代表要选修编号为a的课程，必须先修读编号为b的课程。

Output Format

一个整数，即修完所有课程的最少学期数。

Sample Input1

Sample Output1

Sample Input2

6 0

Sample Output2

Sample Input3

Sample Output3

Limits

0<n<=10000 0<=m<=100000

数据保证合法

ligongzzz's solution

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;

class node {
public:
    int remain = 0;
    vector<int> child;
};

vector<node> nlist;

int bfs(const vector<int> rlist) {
    queue<pii> qdata;
    for(auto root:rlist)
        qdata.push(make_pair(root, 1));

    int ans = 0;
    while (!qdata.empty()) {
        auto temp = qdata.front();
        qdata.pop();
        ans = max(ans, temp.second);

        for (auto& p : nlist[temp.first].child) {
            --nlist[p].remain;
            if (!nlist[p].remain) {
                qdata.push(make_pair(p, temp.second + 1));
            }
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    nlist.resize(n + 1);

    for (; m; --m) {
        int a, b;
        cin >> a >> b;
        ++nlist[a].remain;
        nlist[b].child.emplace_back(a);
    }

    vector<int> rlist;
    for (int i = 1; i <= n; ++i) {
        if (nlist[i].remain == 0)
            rlist.emplace_back(i);
    }

    cout << bfs(rlist);

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

template <class elemType>
class seqQueue {
   private:
    elemType *data;
    int maxSize;
    int front, rear;
    void doubleSpace();

   public:
    seqQueue(int size = maxN);
    ~seqQueue();
    bool isEmpty() const;
    void enQueue(const elemType &);
    elemType deQueue();
    elemType getHead() const;
    int length() const;
};

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
    elemType *tmp = data;
    data = new elemType[maxSize * 2];

    for (int i = 1; i <= maxSize; i++) {
        data[i] = tmp[(front + i) % maxSize];
    }

    front = 0;
    rear = maxSize;
    maxSize *= 2;
    delete[] tmp;
}

template <class elemType>
seqQueue<elemType>::seqQueue(int size) : maxSize(size), front(0), rear(0) {
    data = new elemType[size];
}

template <class elemType>
seqQueue<elemType>::~seqQueue() {
    delete[] data;
}

template <class elemType>
bool seqQueue<elemType>::isEmpty() const {
    return front == rear;
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
    // if ((rear + 1) % maxSize == front) {
    //     doubleSpace();
    // }
    rear = (rear + 1) % maxSize;
    data[rear] = x;
}

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
    front = (front + 1) % maxSize;
    return data[front];
}

template <class elemType>
elemType seqQueue<elemType>::getHead() const {
    return data[(front + 1) % maxSize];
}

template <class elemType>
int seqQueue<elemType>::length() const {
    return ((rear + maxSize - front) % maxSize);
}

struct edgeNode {
    int data;
    edgeNode *next;

    edgeNode(int d = 0, edgeNode *n = 0) : data(d), next(n) {}
};

struct verNode {
    int data;
    int times;
    edgeNode *head;

    verNode(int d = 0, edgeNode *h = 0) : data(d), times(0), head(h) {}
};

int n, m, temp1, temp2, ans = 0, inDegree[maxN] = {0};
verNode *nodes[maxN];
seqQueue<int> que;

void topSort();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        nodes[i] = new verNode(i);
    }

    for (int i = 0; i < m; i++) {
        cin >> temp1 >> temp2;
        nodes[temp2]->head = new edgeNode(temp1, nodes[temp2]->head);
    }

    topSort();

    for (int i = 1; i <= n; i++) {
        ans = (nodes[i]->times > ans) ? nodes[i]->times : ans;
    }

    cout << ans;

    return 0;
}

void topSort() {
    edgeNode *p;
    int current;

    for (int i = 1; i <= n; i++) {
        for (p = nodes[i]->head; p; p = p->next) {
            inDegree[p->data]++;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!inDegree[i]) {
            que.enQueue(i);
            nodes[i]->times++;
        }
    }

    while (!que.isEmpty()) {
        current = que.deQueue();
        for (p = nodes[current]->head; p; p = p->next) {
            if (--inDegree[p->data] == 0) {
                nodes[p->data]->times = nodes[current]->times + 1;
                que.enQueue(p->data);
            }
        }
    }
}

yyong119's solution

#include <cstdio>
#include <queue>
using namespace std;
int n, m, pr, ne, now, next, maxnum;
int indegree[10001];
queue<int> que[2], point[10001];

void topo(int depth, int state) {

    if (que[state].empty()) {
        maxnum = max(maxnum, depth - 1);
        return;
    }
    while (que[state].size()) {
        now = que[state].front(); que[state].pop();
        while (point[now].size()) {
            next = point[now].front();
            indegree[next]--;
            if (indegree[next] == 0) que[1 - state].push(next);
            point[now].pop();
        }
    }
    topo(depth + 1, 1 - state);
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &ne, &pr);
        point[pr].push(ne);
        indegree[ne]++;
    }
    for (int i = 1; i <= n; i++)
        if (!indegree[i]&&point[i].size()) que[0].push(i);
    maxnum = 1;
    topo(1, 0);
    printf("%d\n", maxnum);
    return 0;
}