13010: 【原3010】Complicated Buttons

题目

题目描述

author: zdq 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3010

Description

凯恩在遗迹探险时遇到了n个按钮，刚开始所有按钮都处于开状态，凯恩的经验告诉他把所有按钮都关上会有“好事”发生，可是有些按钮按下时会让其他一些已经闭合的按钮弹开，经过凯恩研究，每个按钮都对应着一个固定的弹开集合，这个按钮按下时，弹开集合中所有的按钮都会变为开状态。现在小k想知道是否能让所有的按钮变为闭状态。如果能，打印最少步数以及方案，否则，打印“no solution”。

Input Format

第一行一个整数n，表示n个按钮。

接下来n行，表示编号为1到n个按钮的弹开集合。

格式为 mi B1 B2 B3 … Bmi

表示编号为i的按钮按下，会让编号为B1 B2 B3… Bmi的按钮弹开（注：其中不会出现重复）。

1 <= n <= 30000
记 M = m1+m2+…+mn，
0 <= M <= 1000000, 对于70%的数据n <= 300

Output Format

如果无解，输出”no solution”。

否则，第一行输出最少步数ans，第二行输出用空格分开的ans个数，表示按顺序按下编号为这些数的按钮就可以解决。

如果有多种方案，输出字典序最小的方案。

Sample Input

6
2 2 3
0
2 4 5
0
0
0

Sample Output

6
1 2 3 4 5 6

yyong119's solution

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define MAX_N 30010
using namespace std;
int n, m, cnt;
int in[MAX_N], ans[MAX_N];
vector<int> link_node[MAX_N];
priority_queue<int, vector<int>, greater<int> > q;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
int main() {
    n = read();
    for (register int i = 1; i <= n; ++i) {
        m = read();
        for (register int j = 0; j < m; ++j) {
            int tmp = read();
            link_node[i].push_back(tmp);
            ++in[tmp];
        }
    }
    for (register int i = 1; i <= n; ++i)
        if (!in[i]) q.push(i);
    while (!q.empty()) {
        int cur = q.top(); q.pop();
        ans[++cnt] = cur;
        for (register int i = 0; i < link_node[cur].size(); ++i) {
            int tmp = link_node[cur][i];
            if (!(--in[tmp]))
                q.push(tmp);
        }
    }
    if (cnt != n) printf("no solution");
    else {
        printf("%d\n", n);
        for (register int i = 1; i <= n; ++i)
            printf("%d ", ans[i]);
    }
    return 0;
}