Fine Logic

登录—专业IT笔试面试备考平台_牛客网

题目大意：有n个数分别为1~n，有m个数值对(u,v)表示u要排在v左边，问至少要多少个排列才能满足所有数值对至少一次

2<=n<=1e6;1<=m<=1e6

思路：如果数值对中要求u在v左边，v在w左边，那么u就得在w左边，所以他们之间具有传递性，同时，如果w要求在u左边，那么1个排列是肯定满足不了的，那么我们从每个数值对的u向v建边，有向图中无环和能用1个排列表示是充分必要条件，而如果有环时，最复杂的情况就是完全图，这是可以用1,2...n和n,n-1...1两个排列表示，可以看出这两个排列已经包含了题目中所有可能的图，我们再来看无环的情况，如果u1和u2都指向v，那么我们要把u1,u2都放在v的左边，所以取拓扑序即可

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll MOD = 1e9 + 7;
vector<int>g[N];
int ind[N];
vector<int>ans;
int n, m;
void init(int x)
{ans.clear();for (int i = 1; i <= x; i++){g[i].clear();ind[i] = 0;}
}
bool bfs()
{//拓扑排序queue<int>q;for (int i = 1; i <= n; i++){if (!ind[i]){q.push(i);ans.push_back(i);}}while (!q.empty()){int u = q.front();q.pop();for (int i = 0; i < g[u].size(); i++){int v = g[u][i];if (!--ind[v]){//将子节点入度为0的放入答案q.push(v);ans.push_back(v);}}}if (ans.size() < n)return 0;//有点入度仍不为0，说明有环return 1;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int t;
t=1;while (t--){	cin >> n >> m;init(n);for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;g[u].push_back(v);ind[v]++;//记录入度}bool temp=bfs();if (!temp){//有环直接输出正序和反序排列cout << 2 << endl;for (int i = 1; i <= n; i++){cout << i << " ";}cout << endl;for (int i = n; i >= 1; i--){cout << i << " ";}cout << endl;continue;}cout << 1 << endl;for (int i = 0; i < ans.size(); i++){cout << ans[i] << " ";}cout << endl;}return 0;
}