## 11709 - Trust groups

Moderator: Board moderators

charles1117
New poster
Posts: 2
Joined: Sun Jan 24, 2010 3:31 pm

### 11709 - Trust groups

I have a problem with 11709.
It seems to be a easy question -- finding out the number of sets where people in the set trust each other
But I am getting WA continuously.

Can anyone help to check my code?
Thanks really much!

Charles

Code: Select all

#include <iostream>
#include <map>
using namespace std;

map<string, int> People;
map<int, bool> m;
int trust[1001][1001];
int group[1001];

int main() {
int P, T, ppl, ppl2;
string temp, temp2;
while (scanf("%d %d", &P, &T), P || T) {
cin.get();
memset(trust, 0, sizeof(trust));
People.clear();
m.clear();
for (int x = 0; x < P; x++) {
getline(cin, temp);
People[temp] = x;
group[x] = x;
}
for (int x = 0; x < T; x++) {
getline(cin, temp);
getline(cin, temp2);
ppl = People[temp];
ppl2 = People[temp2];
trust[ppl][ppl2] = true;
if (group[ppl2] != group[ppl] && trust[ppl2][ppl]) {
for (int y = 0; y < P; y++)
if (group[y] == group[ppl2] && y != ppl2)
group[y] = group[ppl];
group[ppl2] = group[ppl];
}
}
for (int x = 0; x < P; x++)
m[group[x]] = true;
printf("%d\n", (int)m.size());
}
}

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:

### Re: 11709 Trust Groups

Why WA!!! Please give me some test case. Thanks.

Code: Select all

CUT
Last edited by shakil on Sun Feb 07, 2010 5:54 pm, edited 1 time in total.
SHAKIL

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: 11709 Trust Groups

shakil wrote:Why WA!!! Please give me some test case. Thanks.

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct TT
{
char x[30];
};

TT nam[1009];
char temp[30];
long sam[1009][1009],A[1009][1009];
long n,m,i,j,visit[1009],ind[1009];
long p1,p2,count;

int cmp( const void *a, const void *b )
{
TT *p = (TT *)a;
TT *q = (TT *)b;

return ( strcmp(p->x,q->x) );
}

long N(char h1[30])
{
long left,right,mid,h2;
left = 0;
right = n-1;
mid = (left+right)/2;
while(left<=right)
{
h2 = strcmp(h1,nam[mid].x);
if(h2==0)
return mid;
else if(h2>0)
left = mid+1;
else
right = mid-1;
mid = (left+right)/2;
}
return 0;
}

int main()
{

while(1)
{
gets(temp);
sscanf(temp,"%ld %ld",&n,&m);
if(n==0&&m==0)
break;

for(i=0;i<n;i++)
{
gets(nam[i].x);
visit[i]=0;
ind[i]=0;
}

for(i=0;i<n;i++)
for(j=0;j<n;j++)
A[i][j]=0;

qsort(nam,n,sizeof(TT),cmp);

for(i=0;i<m;i++)
{
gets(temp);
p1 = N(temp);
gets(temp);
p2 = N(temp);
if(A[p1][p2]==0)
{
sam[p2][ind[p2]]=p1;
A[p1][p2]=1;
ind[p2]++;

for(j=0;j<ind[p1];j++)
if(A[sam[p1][j]][p2]==0)
{
A[sam[p1][j]][p2]==1;
sam[p2][ind[p2]]=sam[p1][j];
ind[p2]++;
}
}
}

count=0;
for(i=0;i<n;i++)
if(visit[i]==0)
{
visit[i]=1;
count++;
for(j=0;j<n;j++)
if(A[i][j]==1&&A[j][i]==1)
visit[j]=1;
}

printf("%ld\n",count);

}
return 0;
}
Hi, Shakil
try this input
ur code cannot generate proper output
4 4
A, a
B, b
C, c
D, d
A, a
B, b
B, b
C, c
B, b
D, d
C, c
A, a
output: 2
ASU(Sust)

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: 11709 Trust Groups

charles1117 wrote:I have a problem with 11709.
It seems to be a easy question -- finding out the number of sets where people in the set trust each other
But I am getting WA continuously.

Can anyone help to check my code?
Thanks really much!

Charles

Code: Select all

#include <iostream>
#include <map>
using namespace std;

map<string, int> People;
map<int, bool> m;
int trust[1001][1001];
int group[1001];

int main() {
int P, T, ppl, ppl2;
string temp, temp2;
while (scanf("%d %d", &P, &T), P || T) {
cin.get();
memset(trust, 0, sizeof(trust));
People.clear();
m.clear();
for (int x = 0; x < P; x++) {
getline(cin, temp);
People[temp] = x;
group[x] = x;
}
for (int x = 0; x < T; x++) {
getline(cin, temp);
getline(cin, temp2);
ppl = People[temp];
ppl2 = People[temp2];
trust[ppl][ppl2] = true;
if (group[ppl2] != group[ppl] && trust[ppl2][ppl]) {
for (int y = 0; y < P; y++)
if (group[y] == group[ppl2] && y != ppl2)
group[y] = group[ppl];
group[ppl2] = group[ppl];
}
}
for (int x = 0; x < P; x++)
m[group[x]] = true;
printf("%d\n", (int)m.size());
}
}
Hi , Charles
try this input
ur code fail for this input
4 4
A, a
B, b
C, c
D, d
A, a
B, b
B, b
C, c
B, b
D, d
C, c
A, a
output: 2
ASU(Sust)

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 11709 Trust Groups

It seems to me the problem is finding the minimum number of cycles in the forest.
Is I'm right?
How to find minimum number of cycles in the forest...what is the algo????

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11709 Trust Groups

sreejond wrote:It seems to me the problem is finding the minimum number of cycles in the forest.
Is I'm right?
How to find minimum number of cycles in the forest...what is the algo????

I solved this problem with finding SCC..
There is a well known algorithm to find SCC using 2 DFSs..
I think it is called Tarjan's algorithm..

shiam
New poster
Posts: 8
Joined: Mon Mar 14, 2011 6:44 am

### Re: 11709 - Trust Groups

I have Tarjan's algo but still wa can I have some test cases.

Code: Select all

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

/*** typedef ***/

#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
#define stream istringstream
#define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
#define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define INF (1<<30)
#define PI acos(-1.0)
#define pb push_back
#define ppb pop_back
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define memsp(x) mem(x,MEMSET_INF)
#define memdp(x) mem(x,-1)
#define memca(x) mem(x,0)
#define eps 1e-9
#define pii pair<int,int>
#define pmp make_pair
#define ft first
#define sd second
#define pf printf
#define sf scanf
#define vi vector<int>
#define vpii vector<pii>
#define si set<int>
#define msi map<string , int >
#define mis map<int , string >
typedef long long i64;
typedef unsigned long long ui64;

/** function **/

#define SDi(x) sf("%d",&x)
#define SDl(x) sf("%lld",&x)
#define SDs(x) sf("%s",x)
#define SD2(x,y) sf("%d%d",&x,&y)
#define SD3(x,y,z) sf("%d%d%d",&x,&y,&z)

using namespace std;

#define WRITE(f) freopen(f, "w", stdout)
const i64 INF64 = (i64)1E18;

template<class T> inline T gcd(T a,T b) {if(a<0)return
gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
template<class T> inline T sqr(T x){return x*x;}
template<class T> T power(T N,T P){ return (P==0)?  1: N*power(N,P-1); }
template<class T> bool inside(T a,T b,T c){ return (b>=a && b<=c);}

double _dist(double x1,double y1,double x2,double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}
int distsq(int x1,int y1,int x2,int y2){return sqr(x1-x2)+sqr(y1-y2);}
i64 toInt64(string s){i64 r=0;istringstream sin(s);sin>>r;return r;}

double LOG(i64 N,i64 B){	return (log10l(N))/(log10l(B));	}
string itoa(long long a){if(a==0) return "0";string ret;for(long long i=a; i>0; i=i/10) ret.push_back((i%10)+48);reverse(ret.begin(),ret.end());return ret;}

vector< string > token( string a, string b )
{
const char *q = a.c_str();while( count( b.begin(), b.end(), *q ) ) q++;vector< string >
oot;while( *q ) {const char *e = q;while( *e && !count( b.begin(), b.end(),
*e ) ) e++;oot.push_back( string( q, e ) );q = e;while( count( b.begin(),
b.end(), *q ) ) q++;}return oot;
}
int isvowel(char s){s=tolower(s); if(s=='a' || s=='e' || s=='i' || s=='o' || s=='u')return 1; return 0;}
int isupper(char s) {if(s>='A' and s<='Z') return 1; return 0;}
template<class T> struct Fraction{T a,b;Fraction(T a=0,T b=1);string toString();};//NOTES:Fraction
template<class T> Fraction<T>::Fraction(T a,T b){T d=gcd(a,b);a/=d;b/=d;if (b<0) a=-a,b=-b;this->a=a;this->b=b;}
template<class T> string Fraction<T>::toString(){ostringstream sout;sout<<a<<"/"<<b;return sout.str();}
template<class T> Fraction<T> operator+(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b+q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator-(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b-q.a*p.b,p.b*q.b);}
template<class T> Fraction<T> operator*(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.a,p.b*q.b);}
template<class T> Fraction<T> operator/(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b,p.b*q.a);}

//bool operator < ( const node& p ) const {      return dist > p.dist;   }

/** Bitamsk **/

int SET(int N,int pos){	return N=N | (1<<pos);}
int RESET(int N,int pos){	return N= N & ~(1<<pos);}
int check(int N,int pos){	return (N & (1<<pos));}
int toggle(int N,int pos){if(check(N,pos))return N=RESET(N,pos);return N=SET(N,pos);}
void PRINTBIT(int N){	printf("("); for(int i=6;i>=1;i--)	{bool x=check(N,i);cout<<x;}	puts(")");}

const i64 INFFF=1e16;

#define N 1010
int n,gp;
msi m;
vi G[N];

int Stack[N], top;
bool Onstack[N];
int Component[N];
int idx, components;

void tarjan(int u) {
int v, i;
Stack[top++] = u;
Onstack[u] = 1;
for(i = 0; i < (int)G[u].size(); i++) {
v = G[u][i];
if(Index[v]==-1) {
tarjan(v);
}
}
components++;
do {
v = Stack[--top];
Onstack[v] = 0;
} while(u != v);
}
}

int main()
{
while(SD2(n,gp)&&n&&gp)
{
getchar();
int id=1;
char ch[200];
rep(i,n)
{
gets(ch);
string s(ch);
m[s]=id++;
}
rep(i,gp)
{
gets(ch);
string s1(ch);
gets(ch);
string s2(ch);
int u = m[s1], v = m[s2];
G[u].pb(v);
}
components = top = idx = 0;
memdp(Index);
memca(Onstack);

for(int i = 1; i <= n; i++)
if(Index[i]==-1)
tarjan(i);

m.clear();
int i=n+2;
while(i--) G[i].clear();

pf("%d\n",components);
}
return 0;
}

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: 11709 - Trust groups

any idea why this code gets WA ??

Code: Select all

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
int n, m, vist[N], low[N], disc[N], in[N], id, ans;
char s[11], x[11];
map<string, int> val;
vector<vector<int> > arr;
vector<int> stk;
void dfs(int x) {
static int tim = 0;
low[x] = disc[x] = ++tim;
stk.push_back(x);
in[x] = id;
for (int i = 0, ln = arr[x].size(); i < ln; ++i) {
int y = arr[x][i];
if (disc[y] == -1) {
dfs(y);
low[x] = min(low[x], low[y]);
} else if (in[y] == id)
low[x] = min(low[x], disc[y]);
}
if (low[x] == disc[x]) {
++ans;
int y;
do {
y = stk.back();
stk.pop_back();
in[y] = 0;
} while (y != x);
}
}
int main(int argc, char **argv) {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
while (scanf("%d %d\n", &n, &m) > 0 && n) {
arr.clear();
arr.resize(n + 1);
stk.clear();
val.clear();
memset(disc,-1,sizeof disc);
ans = 0;
++id;
for (int i = 0; i < n; ++i) {
gets(s);
val[s] = i;
}
while (m--) {
gets(s);
gets(x);
arr[val[s]].push_back(val[x]);
}
for (int i = 0; i < n; ++i)
if (disc[i] == -1)
dfs(i);
printf("%d\n", ans);
}
return 0;
}

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

### Re: 11709 - Trust groups

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: 11709 - Trust groups

will i tried before and it did not terminate
I found the bug thanks