## 1197 - The Suspects

Moderator: Board moderators

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### 1197 - The Suspects

Acc
Last edited by mahade hasan on Sat Sep 29, 2012 5:59 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1197 - The Suspects

mahade hasan wrote:why why WAA plz help me
Try input:

Code: Select all

``````2 1
2 0 1
2 1
2 0 1
0 0``````
Check input and AC output for thousands of problems on uDebug!

Muftee_Ruet
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

### Re: 1197 - The Suspects

Simple DFS problem.

Run DFS from node 0 to find out how many nodes are connected with node 0.
Aware of input : m can be 0.

Happy coding.

vellvisher
New poster
Posts: 2
Joined: Fri Jan 25, 2013 1:28 pm

### 1197 - The Suspects

I am getting RE continuously..

Code: Select all

``````#include<iostream>
#include<vector>
using namespace std;
typedef vector<int> vi;
class UnionFind{
private: vi p;

public: UnionFind(int N) { p.assign(N+1,-1);}
void reset(int N) { p.clear(); p.assign(N+1, -1);}
int findSet(int i) {if (p[i] < 0) return i; else return p[i] = findSet(p[i]);}
void unionSet(int i, int j) { int x = findSet(i), y = findSet(j); if(p[x] < p[y]) {
p[x] += p[y];p[y] = x; } else {p[y] += p[x];p[x] = y;}}};
UnionFind uf(1);

int main() {
int n, m;
cin >> n >> m;
while(n) {
uf.reset(n);
for(int i = 0; i < m; i++) {
int k, r,s;
cin >> k;
if(k) {
cin >> r;
for(int i = 1; i < k; i++) {
cin >> s;
if(r+1 > n || s+1 > n) continue;
uf.unionSet(r+1, s+1);
}
}
}
int count = 0;
for(int i = 1; i <= n; i++) {
count+= uf.findSet(i) == uf.findSet(1);
}
cout << count << endl;
cin >> n >> m;
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1197 - The Suspects

Check input and AC output for thousands of problems on uDebug!

vellvisher
New poster
Posts: 2
Joined: Fri Jan 25, 2013 1:28 pm

### Re: 1197 - The Suspects

V

raiyan21
New poster
Posts: 2
Joined: Wed Jan 30, 2013 12:08 pm

### Re: 1197 - The Suspects

I am getting WA. I tried hard to find the bug. But I failed. Here is my code.

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 1147483647
#define INF_MIN -1147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i <= (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, (s), sizeof (a))

using namespace std;
map<int,int> pset;
int findSet(int n)
{
if(n==pset[n])
return n;
return (pset[n]= findSet(pset[n]));
}
void merge(int i, int j)
{
pset[findSet(i)] = findSet(j);
}
int sizeOfSet(int n)
{
int r = findSet(n);
int t, cnt = 0;;
map<int, int>:: iterator it;
for(it= pset.begin(); it!=pset.end(); it++)
{
t = it->second;
if(t==r) cnt ++;
}
return cnt;
}
int main()
{
int i,j,k,n,m,u,v;
set<int> node;
set<int>:: iterator it;
bool done[30000];
while(scanf("%d %d", &n, &m) && (n||m))
{
/*for(it=node.begin(); it!=node.end(); it++)
{
i = *it;
}*/
//For(i,0,504)
Set(done, false);
pset.clear();
if(m==0) {
printf("1\n");
continue;
}
vector<int> temp;
//node.clear();
For(i,1,m)
{
cin >> u;
temp.clear();
For(j,0,u-1)
{
cin >> v;
if(done[v]==false){
pset[v] = v;
done[v] = true;
}
temp.push_back(v);
}
int p,q;
p = temp[0];
For(k,1,temp.size()-1)
{
q = temp[k];
merge(p,q);
}
}

int ans = sizeOfSet(0);
cout << ans << endl;
}

return 0;
}
``````
It will be a great help if anyone give some sample test case so that I can find the bug. Thanx.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1197 - The Suspects

Why is pset a map and not an array?
Check input and AC output for thousands of problems on uDebug!

light1k5
New poster
Posts: 1
Joined: Sun Jun 28, 2015 11:33 am

### UVa 1197 - The Suspects : Wrong Answer

Below is my implementation to keep track of the size of each tree in the disjoint set forest.

Can you please tell me what is wrong with it ? I am trying to solve UVa problem https://goo.gl/ZiQCyH

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;

class Node {
public :
int id;
Node *parent;
unsigned long long rank;

Node(int id) {
this->id = id;
// this->data = data;
this->rank =1; //size here
this->parent = this;
}
friend class DisjointSet;
};

class DisjointSet {
unordered_map<int,Node*> nodesMap;

Node *find_set_helper(Node *aNode) {

if (aNode == aNode->parent) {
return aNode->parent;
}
return find_set_helper(aNode->parent);
}

if( xNode->rank > yNode->rank) {
yNode->parent = xNode;
xNode->rank += yNode->rank;
}
// else if(xNode-> rank < yNode->rank){
//     xNode->parent = yNode;
//     yNode->rank += xNode->rank;
// }
else {
xNode->parent = yNode;
yNode->rank += xNode->rank;
}
}
public:
DisjointSet() {

}

for(int i=0;i<sz;i++)
this->make_set(i);
}

void make_set(int id) {
Node *aNode = new Node(id);
this->nodesMap.insert(make_pair(id,aNode));
}

void Union(int xId, int yId) {
Node *xNode = find_set(xId);
Node *yNode = find_set(yId);

if(xNode && yNode)
}

Node* find_set(int id) {
unordered_map<int,Node*> :: iterator itr = this->nodesMap.find(id);
if(itr == this->nodesMap.end())
return NULL;

return this->find_set_helper(itr->second);
}

~DisjointSet(){
unordered_map<int,Node*>::iterator itr;
for(itr = nodesMap.begin(); itr != nodesMap.end(); itr++) {
delete (itr->second);
}
}

};
int main() {

int n,m,k,first,cur;

//freopen("in.in","r",stdin);

scanf("%d %d",&n,&m);

while(n != 0 || m != 0) {

DisjointSet *ds = new DisjointSet();

//printf("\n n = %d m = %d",n,m);

for(int i=1;i<=m;i++) {
scanf("%d",&k);
//printf("\nk=%d",k);
if ( k > 0 ) {

scanf("%d",&first);
for(int j=2;j<=k;j++) {
scanf("%d",&cur);
ds->Union(first,cur);
}
}
}

Node *zeroSet = ds->find_set(0);
// unsigned long long count = ds->getCount(zeroSet->id);
printf("%llu\n",zeroSet->rank);
delete ds;

scanf("%d %d",&n,&m);
}

return 0;
}``````

The link function in the above code does the job of updating the tree size.

The solution to the problem is to find the set which elements 0 belongs to and get the size of the representative element of the set. But I am getting wrong answer with this code.