Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <queue>
- using namespace std;
- vector <vector <int> > graph;
- vector <bool> used;
- void dfs (int i) {
- used[i] = true;
- for (int j = 0; j < graph[i].size(); ++j) {
- if (!used[graph[i][j]]) {
- dfs(graph[i][j]);
- }
- }
- }
- bool checkGraph (int n) {
- for (int i = 0; i < n; ++i) {
- if (!used[i])
- return 0;
- }
- return 1;
- }
- int main(int argc, const char * argv[]) {
- ifstream fin("/Users/ilabockov/Desktop/xcode/SWIFT/SwiftBook/graphs/graphs/input.txt");
- ofstream fout("/Users/ilabockov/Desktop/xcode/SWIFT/SwiftBook/graphs/graphs/output.txt");
- int n;
- int maxTime (0), firstDomino;
- fin >> n;
- graph.resize(n);
- used.resize(n);
- for (int i = 0; i < n; ++i) {
- int m;
- fin >> m;
- for (int i = 0; i < m; ++i) {
- int buf;
- fin >> buf;
- graph[i].push_back(buf - 1);
- }
- }
- fin.close();
- dfs(0);
- for (int i = 0; i < n; ++i) {
- if (!used[i]) {
- fout << "impossible";
- fout.close();
- return 0;
- }
- used[i] = false;
- }
- int flag = 0;
- for (int i = 0; i < n; ++i) {
- int time = 0;
- // queue <int> myQueue;
- // if (!used[i]) {
- // myQueue.push(i);
- // used[i] = true;
- // while (!myQueue.empty()) {
- // int i = myQueue.front();
- // myQueue.pop();
- // for (int j = 0; j < graph[i].size(); ++j) {
- // if (!used[graph[i][j]]) {
- // myQueue.push(graph[i][j]);
- // used[graph[i][j]] = true;
- // time ++;
- // } else time --;
- // }
- // }
- // }
- queue <int> myQueue;
- myQueue.push(i);
- used[i] = true;
- while (true) {
- queue <int> bufQueue;
- while (!myQueue.empty()) {
- int i = myQueue.front();
- myQueue.pop();
- for (int j = 0; j < graph[i].size(); ++j) {
- if (!used[graph[i][j]]) {
- bufQueue.push(graph[i][j]);
- used[graph[i][j]] = true;
- }
- }
- }
- if (bufQueue.empty()) {
- break;
- }
- time++;
- myQueue = bufQueue;
- }
- if (time >= maxTime && checkGraph(n)) {
- maxTime = time;
- firstDomino = i;
- flag = 1;
- }
- for (int i = 0; i < n; ++i) {
- used[i] = false;
- }
- }
- if (flag == 1) {
- fout << maxTime << endl << firstDomino + 1;
- } else {
- fout << "impossible";
- }
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement