PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Saytabrat Panda
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy
PREREQUISITES:
Graph Theory, Bipartite Graphs
PROBLEM:
Representing the citizens as nodes , the problem reduces to :
Given N citizens,where some pair of citizens grudge against each other. Find out if the citizens can be put into two groups such that no two citizens belonging to the same group have a grudge against each other.
QUICK EXPLANATION:
Check if the graph formed out of considering citizens as nodes and grudges as edges is bipartite.
EXPLANATION:
A naive solution can be formed by checking each pair and greedily assigning them groups but will require O(N^2) time which isn’t fast enough.
An optimal solution is:
If we represent the citizens as nodes, we will have a graph where if two nodes (i.e citizens) have a grudge between themselves there will be an undirected edge between them.
Now we have to put each of the nodes into one of two groups such that no two nodes belonging to the same group have an edge between them.
This is a standard case of bipartite checking.
You may refer this link to read more about bipartite checking.
It can be solved in O(N+K) which is fast enough to get AC.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> graph[100005];
int32_t main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
graph[i].clear();
for(int i=0;i<k;i++)
{
int u,v;
cin>>u>>v;
u--,v--;
graph[u].push_back(v);
graph[v].push_back(u);
}
int color[n];
memset(color,-1,sizeof(color));
int ok=1;
queue<int> q;
for(int node=0;node<n;node++)
{
if(color[node]==-1)
{
q.push(node);
color[node] = 0;
while (!q.empty())
{
int v = q.front();
q.pop();
for (int u : graph[v])
{
if (color[u] == -1)
{ color[u] = color[v] ^ 1; q.push(u);}
else if(color[u] == color[v])ok=0;
}
}
}
}
if(ok==1)cout<<"possible\n";
else cout<<"impossible\n";
}
}
Tester's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
static class Graph{
static int color[],V;
static ArrayList<Integer> l[];
public Graph(int v){
V=v;
l=new ArrayList[V+1];
for(int i=0;i<=V;i++)
l[i]=new ArrayList<Integer>();
color=new int[V+1];
Arrays.fill(color,-1);
}
void addEdge(int u,int v){
l[u].add(v);
l[v].add(u);
}
boolean bfs(){
boolean ret=true;
for(int i=1;i<=V;i++){
if(color[i]!=-1)
continue;
ret=ret && isBipartite(i);
}
return ret;
}
boolean isBipartite(int s){
Queue<Integer> q=new LinkedList<>();
q.add(s);
color[s]=0;
while(!q.isEmpty()){
int u=q.poll();
ArrayList<Integer> x=l[u];
for(Integer v: x){
if(color[v]==-1){
color[v]=1-color[u];
q.add(v);
}
else if(color[v]==color[u]){
return false;
}
}
}
return true;
}
}
static int sum_n=0,sum_k=0;
public static void process()throws IOException
{
int n=ni(),k=ni(); sum_n+=n; sum_k+=k;
assert (n>1e5 || k>1e5):"sum of n or k > 1e5";
Graph g=new Graph(n);
for(int i=1;i<=k;i++) g.addEdge(ni(),ni());
pn(g.bfs()?"possible":"impossible");
}
static FastReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
out = new PrintWriter(System.out);
sc=new FastReader();
long s = System.currentTimeMillis();
int t=1;
t=ni();
while(t-->0)
process();
out.flush();
System.err.println(System.currentTimeMillis()-s+"ms");
System.out.close();
}
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);System.out.flush();}
static int ni()throws IOException{return Integer.parseInt(sc.next());}
static long nl()throws IOException{return Long.parseLong(sc.next());}
static double nd()throws IOException{return Double.parseDouble(sc.next());}
static String nln()throws IOException{return sc.nextLine();}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
static boolean multipleTC=false;
static long mod=(long)1e9+7l;
static<T> void r_sort(T arr[],int n){
Random r = new Random();
for (int i = n-1; i > 0; i--){
int j = r.nextInt(i+1);
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Arrays.sort(arr);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next(){
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str = "";
try{
str = br.readLine();
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
