Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector<int> find_the_least(int n, bool *graph)
- {
- bool flag = true;
- vector<int> ans;
- for(int i = 0; i < n; i++)
- {
- for(int j = 0; j < n; j++)
- {
- if(graph[j * n + i])
- {
- flag = false;
- break;
- }
- }
- if(flag)
- ans.push_back(i);
- flag = true;
- }
- return ans;
- }
- void create_string(int n, bool *graph, vector<vector<int> > *allPaths, int i, vector<int> path)
- {
- path.push_back(i + 1);
- if(path.size() < n)
- {
- bool gr[n * n];
- for(int j = 0; j < n * n; j++)
- gr[j] = graph[j];
- for(int j = 0; j < n; j++)
- gr[i * n + j] = false;
- gr[i * n + i] = true;
- vector<int> tmp = find_the_least(n, gr);
- for(int j = 0; j < tmp.size(); j++)
- {
- create_string(n, gr, allPaths, tmp[j], path);
- }
- }
- else
- {
- allPaths->push_back(path);
- }
- }
- int main()
- {
- vector<vector<int> > paths;
- int n, m, a, b;
- cin >> n >> m;
- bool graph[n * n];
- for(int i = 0; i < n * n; i++)
- graph[i] = false;
- for(int i = 0; i < m; i++)
- {
- cin >> a >> b;
- graph[(a - 1) * n + (b - 1)] = true;
- }
- vector<int> tmp = find_the_least(n, graph);
- vector<int> path;
- for(int i = 0; i < tmp.size(); i++)
- create_string(n, graph, &paths, tmp[i], path);
- if(paths.size() > 0)
- {
- cout << paths.size() << endl;
- for(int i = 0; i < paths.size(); i++)
- {
- for(int j = 0; j < n; j++)
- cout << paths[i][j] << " ";
- cout << endl;
- }
- }
- else
- {
- cout << "no" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement