## 11709 - Trust Groups

Moderator: Board moderators

### 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());   }}`
charles1117
New poster

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

### 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
shakil
Learning poster

Posts: 74
Joined: Sat Jul 15, 2006 6:28 am

### 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)
robot
New poster

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

### 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????

sreejond
New poster

Posts: 32
Joined: Fri May 23, 2008 6:16 pm

### 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..
helloneo
Guru

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

### 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 READ(f) freopen(f, "r", stdin)#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)returngcd(-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:Fractiontemplate<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 1010int n,gp;msi m;vi G[N];int Stack[N], top;int Index[N], Lowlink[N];bool Onstack[N];int Component[N];int idx, components;void tarjan(int u) {   int v, i;   Index[u] = Lowlink[u] = idx++;   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);         Lowlink[u] = min(Lowlink[u], Lowlink[v]);      }      else if(Onstack[v]) Lowlink[u] = min(Lowlink[u], Index[v]);   }   if(Lowlink[u] == Index[u]) {      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);        memsp(Lowlink);        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;}`