11237: 【原1237】Courses

题目描述

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

Description

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

5 4
1 2
2 3
3 4
4 5

5

6 0

1

6 3
1 2
1 3
4 1

3

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();
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>
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;

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;
}

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;
}