11709 - Trust groups

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11709 - Trust groups

Post by charles1117 » Sun Jan 24, 2010 3:41 pm

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
Location: CUET , bangladesh
Contact:

Re: 11709 Trust Groups

Post by shakil » Sat Feb 06, 2010 7:34 pm

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

Post by robot » Sun Feb 07, 2010 8:50 am

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

Post by robot » Sun Feb 07, 2010 8:57 am

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)

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

Re: 11709 Trust Groups

Post by sreejond » Sun Feb 21, 2010 9:16 am

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

Thnx in advance.

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

Re: 11709 Trust Groups

Post by helloneo » Sun Feb 21, 2010 2:15 pm

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

Thnx in advance.
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

Post by shiam » Sun Aug 12, 2012 11:50 pm

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)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;
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;
}

:( Thanks in advance.

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

Re: 11709 - Trust groups

Post by just_yousef » Sat Feb 14, 2015 1:44 am

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

Post by brianfry713 » Wed Feb 18, 2015 12:13 am

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

Post by just_yousef » Wed Feb 18, 2015 9:55 am

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

Post Reply

Return to “Volume 117 (11700-11799)”