Cod sursa(job #2406759)

Utilizator andrei.seritanAndrei Seritan andrei.seritan Data 16 aprilie 2019 10:25:19
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int kNmax = 100005;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
  int index = 0;
	vector<int> adj[kNmax];
  vector<vector<int>> sol;
  vector<int> level;
  vector<int> lowlink;
  vector<int> stack;

	void read_input() {
		ifstream fin("biconex.in");
		fin >> n >> m;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
    level.resize(n + 1, -1);
    lowlink.resize(n + 1, -1);
		fin.close();
	}

	vector<vector<int>> get_result() {
		/*
		TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
		de adiacenta in adj.
		*/
    // sol.clear();
    index = 0;
    for (int i = 1; i <= n; ++i) {
      if (level[i] == -1) {
        tarjan(i);
      }
    }
		return sol;
	}

  void tarjan(int source) {
    level[source] = index;
    lowlink[source] = index;
    index = index + 1;
    stack.push_back(source);

    for (auto neighbour : adj[source]) {
      if (level[neighbour] == -1) {
        tarjan(neighbour);
        lowlink[source] = min(lowlink[source], lowlink[neighbour]);

        if (lowlink[neighbour] >= level[source]) {
          vector<int> part_sol;
          part_sol.push_back(source);
          while (stack.back() != neighbour) {
            part_sol.push_back(stack.back());
            stack.pop_back();
          }
          part_sol.push_back(stack.back());
          stack.pop_back();
          sol.push_back(part_sol);
        }
      } else {
        lowlink[source] = min(lowlink[source], level[neighbour]);
      }
    }
  }

	void print_output(vector<vector<int>> result) {
		ofstream fout("biconex.out");
    fout << result.size() << '\n';
		for (const auto& ctc : result) {
			for (int nod : ctc) {
				fout << nod << ' ';
			}
			fout << '\n';
		}
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}