CodeChef submission 131046 (C++ 4.0.0-8) plaintext list. Status: WA, problem J6, contest NOV09. By CarbonUnit (CarbonUnit), 2009-11-11 14:44:15.
#include <iostream>
#include <map>
#include <vector>
#include <stack>
 
using namespace std;
 
int n; // politicians
int m; // lines of evidence
 
// Bit flags
// 1=vertex is on stack
class Vertex
{
public:
  int component, origin;
  int flag;
  int ndex, lowlink;
  vector<Vertex *> e;
};
 
void ToID(int a, int &id)
{
  if(a<0){
    // -1 -> 1, -2 -> 3
    id=-1-2*a;
  }else{
    // 1 -> 0, 2 -> 2
    id=2*a-2;
  }
}
 
Vertex *va;
Vertex *GetVertex(int id){ return va+id; }
 
stack<Vertex *> s;
int ndex;
int component, origin;
 
void Tarjan(Vertex *v)
{
  v->ndex = ndex;
  v->lowlink = ndex;
  ++ ndex;
  s.push(v);
  v->flag = 1; // mark as stacked
  vector<Vertex*>::iterator i;
  for(i=v->e.begin();i!=v->e.end();++i){
    Vertex *v1=*i;
    if(v1->ndex==-1){
      Tarjan(v1);
      v->lowlink = min(v->lowlink,v1->lowlink);
    }else if(v1->flag){
      v->lowlink = min(v->lowlink,v1->ndex);
    }
  }
  if(v->lowlink==v->ndex){
    ++component;
    Vertex *v1;
    do{
      v1=s.top();
      s.pop();
      v1->flag = 0;
      v1->component = component;
      v1->origin = origin;
    }while(v1!=v);
  }
}
 
int Search()
{
  // Find strongly connected components
  component = ndex = 0;
  for(int in=0; in<n*2; in++){
    origin = in;
    Vertex *v = GetVertex(in);
    if(v->component==0){
      Tarjan(v);
    }
  }
  // Check for unsatisfiability
  for(int in=0; in<n*2; in+=2){
    Vertex *v0 = GetVertex(in); // A
    Vertex *v1 = GetVertex(in+1); // Not A
    if(v0->component==v1->component)
      return 0;
  }
  // Check for uniqueness
  for(int in=0; in<n*2; in+=2){
    Vertex *v0 = GetVertex(in); // A
    Vertex *v1 = GetVertex(in+1); // Not A
    if(v0->origin!=v1->origin)
      return 2;
  }
  return 1;
}
 
int main(int argc, char **argv)
{
  int t;
  cin >> t;
  for(int it=0; it<t; ++it){
    cin >> n >> m;
    va = new Vertex[n*2];
    for(int in=0; in<n*2; ++in){
      Vertex *v = GetVertex(in);
      v->flag = 0;
      v->ndex = v->lowlink = -1;
      v->component = 0;
      v->e.clear();
    }
    for(int ie=0; ie<m; ++ie){
      int a, b, aid, bid;
      cin >> a >> b;
      ToID(a,aid);
      ToID(b,bid);
      Vertex *a0=GetVertex(aid^1);
      Vertex *a1=GetVertex(aid);
      Vertex *b0=GetVertex(bid^1);
      Vertex *b1=GetVertex(bid);
      a0->e.push_back(b1);
      b0->e.push_back(a1);
    }
    int found = Search();
    delete[] va;
    if( found == 0 )
      cout << "CONFLICT" << endl;
    else if( found == 1 )
      cout << "UNIQUE" << endl;
    else
      cout << "MULTIPLE" << endl;
  }
  return 0;
}