Cod sursa(job #2205104)

Utilizator Fulga.AlinFulga Alin Fulga.Alin Data 17 mai 2018 22:55:35
Problema 2SAT Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 4.38 kb
#include <fstream>
#include <vector>
#include <stack>
#include <deque>
std::ifstream in("2sat.in");
std::ofstream out("2sat.out");
#define MAX_N 200001
#define OFFSET 100000
long n, m, x, y;
std::vector<long> adjList[MAX_N];
std::vector<long> adjListT[MAX_N];
std::vector<long> components[MAX_N];
std::vector<long> component(MAX_N);
std::vector<bool> visited(MAX_N);
std::vector<int> degree(MAX_N);
std::vector<int> results(MAX_N);
std::stack<long> vertices;
std::deque<long> sortedVertices;
std::deque<long> zeroDegreeComponents;
bool satisfiable = true;
long nrComponents;
void topological(long start) {
  vertices.push(start);
  bool isVisited;

  while(!vertices.empty()) {
    long topOfStack = vertices.top();
    isVisited = true;
    visited[topOfStack] = true;
    auto itr = adjList[topOfStack].begin();
    while (itr != adjList[topOfStack].end()) {
      if(!visited[*itr]) {
        vertices.push(*itr);
        isVisited = false;
      }
      ++itr;
    }
    if (isVisited) {
      vertices.pop();
      sortedVertices.push_front(topOfStack);
    }
  }

}
void dfsT(long start) {
  vertices.push(start);
  while(!vertices.empty()) {
    long topOfStack = vertices.top();
    vertices.pop();
    if (!visited[topOfStack]) {
      visited[topOfStack] = true;
    }
    component[topOfStack] = nrComponents;
    components[nrComponents].push_back(topOfStack);
    auto itr = adjListT[topOfStack].begin();
    while (itr != adjListT[topOfStack].end()) {
      if(!visited[*itr]) {
        vertices.push(*itr);
      }
      ++itr;
    }
  }
}
long index(long indexIn) {
  return (indexIn>0) ? indexIn-1 : (-indexIn - 1 + OFFSET);
}
void handleInput() {
  in >> n >> m;
  for (int i = 0; i < m; i++) {
    in >> x >> y;
    adjList[index(-x)].push_back(index(y));
    adjList[index(-y)].push_back(index(x));
    adjListT[index(y)].push_back(index(-x));
    adjListT[index(x)].push_back(index(-y));
  }
}
void topologicalSort() {
  for (int i = 0; i < n; i++) {
    visited[i] = false;
    visited[i + OFFSET] = false;
  }
  while (sortedVertices.size() < n * 2) {
      for (int i = 0; i < n; i++) {
        if (!visited[i]) {
          topological(i);
        }
        else if(!visited[i + OFFSET]) {
          topological(i + OFFSET);
        }
      }
  }
}
void findStronglyConnectedComponents() {
  for (int i = 0; i < n; i++) {
    visited[i] = false;
    visited[i + OFFSET] = false;
  }
  while (!sortedVertices.empty()) {
    if (!visited[*sortedVertices.begin()]) {
      dfsT(*sortedVertices.begin());
      nrComponents++;
    }
    sortedVertices.pop_front();
  }
}
void findSatisfiableArguments() {
  for (int i = 0; i < n; i++) {
    auto itr = adjList[i].begin();
    while (itr != adjList[i].end()) {
      if(component[*itr] != component[i]) {
        degree[component[*itr]] ++;
      }
      ++itr;
    }
    itr = adjList[i + OFFSET].begin();
    while (itr != adjList[i + OFFSET].end()) {
      if(component[*itr] != component[i + OFFSET]) {
        degree[component[*itr]] ++;
      }
      ++itr;
    }
  }
  for (int i = 0; i < nrComponents; i++) {
    if (degree[i] == 0) {
      zeroDegreeComponents.push_back(i);
    }
  }
  while (!zeroDegreeComponents.empty()) {
    long comp = *zeroDegreeComponents.begin();
    zeroDegreeComponents.pop_front();
    auto itr = components[comp].begin();
    while (itr != components[comp].end()) {
      long predicate = (*itr >= OFFSET) ? *itr - OFFSET : *itr;
      if (results[predicate] == 0) {
        if (*itr >= OFFSET) {
          results[predicate] = 2;
        }
        else {
          results[predicate] = 1;
        }
      }
      ++itr;
    }
    itr = components[comp].begin();
    while (itr != components[comp].end()) {
      auto itr2 = adjList[*itr].begin();
      while (itr2 != adjList[*itr].end()) {
        if (component[*itr] != component[*itr2]) {
          degree[component[*itr2]]--;
          if (degree[component[*itr2]] == 0) {
            zeroDegreeComponents.push_back(component[*itr2]);
          }
        }
        ++ itr2;
      }
      ++ itr;
    }
  }
}
void showSolutions() {
  for (int i = 0; i < n; i++) {
    if (component[i] == component[i + OFFSET]) {
      satisfiable = false;
    }
  }
  if (satisfiable) {
    findSatisfiableArguments();
    for (int i = 0; i < n; i++) {
      out << results[i]-1 << " ";
    }
  }
  else {
    out << "-1";
  }
}

int main() {
  handleInput();
  topologicalSort();
  findStronglyConnectedComponents();
  showSolutions();
}