Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- struct edge{
- int v;
- bool only;
- bool used;
- };
- vector<vector<edge> > edges;
- vector<int> parent;
- vector<bool> w;
- vector<bool> _w;
- vector<int> color;
- vector<int> history;
- int n, m;
- int f = 0;
- void dump_history(){
- f++;
- cout << "#" << ++f << " : ";
- for (int i = 0; i < history.size(); i++)
- cout << history[i] << " ";
- cout << endl;
- }
- int dfs(int v, int u){
- _w[v] = true;
- if (w[v]) return -1;
- //history.push_back(v);
- //dump_history();
- int _buf = parent[v];
- if (parent[v] == -2) parent[v] = u; else
- if (parent[v] != u) parent[v] = -1;
- {
- w[v] = true;
- for (int i = 0; i < edges[v].size(); i++){
- if (edges[v][i].used) continue;
- int q = edges[v][i].v;
- int result = dfs(q, v);
- if (result == 0) edges[v][i].used = true;
- }
- w[v] = false;
- }
- //history.pop_back();
- return 0;
- }
- int _find(int u, int v){
- for (int i = 0; i < edges[u].size(); i++)
- if (edges[u][i].v == v)
- return i;
- }
- void colorise(int v, int c){
- if (w[v]) return;
- color[v] = c;
- w[v] = true;
- for (int i = 0; i < edges[v].size(); i++){
- if (edges[v][i].only == false) {
- colorise(edges[v][i].v, c);
- }
- }
- }
- int main()
- {
- cin >> n >> m;
- edges.resize(n);
- edge e; e.only = false; e.used = false;
- int u, v;
- for (int i = 0; i < m; i++){
- cin >> u >> v;
- //u = (rand()*rand()+rand())%n; v = rand()%n;
- u--; v--;
- e.v = v; edges[u].push_back(e);
- e.v = u; edges[v].push_back(e);
- }
- parent.resize(n, -2);
- w.resize(n, false);
- _w.resize(n, false);
- for (int i = 0; i < n; i++){
- if (!(_w[i]))
- dfs(i, -2);
- parent[0] = -1;
- }
- /*for (int i = 0; i < n; i++){
- cout << parent[i] << " ";
- } cout << endl;*/
- for (int i = 0; i < n; i++){
- if (parent[i] >= 0) {
- int r = _find(i, parent[i]);
- edges[i][r].only = true;
- r = _find(parent[i], i);
- edges[parent[i]][r].only = true;
- }
- }
- color.resize(n, -1);
- int _color = 0;
- for (int i = 0; i < n; i++) w[i] = false;
- for (int i = 0; i < n; i++){
- if (color[i] == -1) {
- _color++;
- colorise(i, _color);
- }
- }
- for (int i = 0; i < n; i++){
- cout << color[i] << " ";
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement