10973 - Triangle Counting

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

Moderator: Board moderators

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Thu Jan 19, 2006 9:20 pm

Hi,

I've acc but in 7,8 sec. My prog is in general O(VE) but with some optimalization. I have one question is there an O(V^2) algo or O(VE) with super optimalization?

Probably i should use this "You are assured that there is no edge in this graph that is the member of more than 2 triangles" in very smart way, but at this time i've no idea, any hints?

thx

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Tue Jan 24, 2006 7:01 am

Monsoon:

The first algorithm that comes to our mind is what follows:

Let M be the adjacency matrix of the graph, n the number of nodes...

int c2 = 0;

for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (M[j] == 1)
{
int c1 = 0;
for (int k = j + 1; k <= n; k++)
if (M[j][k] == 1 && M[k] == 1)
{
c1++;
if (c1 == 2)
break;

}
c2 += c1;
}

printf("%d\n", c2);

The line marked in red is what you can use to make your algorithm faster..., that's why it's so important...

Now try to make the same thing in another way..., this will get TLE of course :wink:

Hope this helps,

Yandry.

sluga
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia

Post by sluga » Tue Jan 24, 2006 12:15 pm

I solved it in O( VE ) but added a line which stops counting triangles for some edge after I have found 2 triangles.
It gets TLE
This is the important part of my code:

Code: Select all

        int cnt = 0;
        for( int i = 0; i < ( int )E.size(); ++i ) {
            int t_cnt = 0;
            for( int j = 0; t_cnt < 2 && j < v; ++j )
                t_cnt += ( path[E[i].first][j] && path[j][E[i].second] );
            cnt += t_cnt;
        }
How can I make it faster?
I know it is too slow for bipartite graphs.
A sta da radim

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Tue Jan 24, 2006 12:41 pm

i made also BFS and give all nodes v length D[v] from any start node(watch out for not connected graphs). And we can see that in triangle is at least one edge between nodes e1-e2 that D[e1]==D[e2]. So we can check in your first loop only that type of edges. And we should watch out about triangle(v1,v2,v3) that D[v1]==D[v2]==D[v3].

But it gave me only time about 7 sec,

if anybody knows better algo please give me a hint? :)

To neno_uci:

thx for your post, but i have this condition in my solution

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jan 24, 2006 4:53 pm

This is algorithm of my solution:

Code: Select all

for x=1..n, adj[x] is the set { y: y>x and (x,y) is in E }.
w[1..n] is an array of integers, initially filled with zeroes

count = 0
for x = 1 to n:
	for each y in adj[x]: w[y] = 1
	for each y in adj[x]:
		for each z in adj[y]:
			count += w[z]
	for each y in adj[x]: w[z] = 0
return count
It gave me about 1.5 sec runtime. (asm and faster I/O cut that down to 0.180s.)

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Tue Jan 24, 2006 5:05 pm

thx a lot :D

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Wed Jan 25, 2006 12:03 am

I did exactly what mf did..., but I did not want to be so explicit..., I wanted you to find it by yourself..., hehehe, best regards,

Yandry. :wink:

imnew
New poster
Posts: 5
Joined: Sun Feb 12, 2006 6:37 am

10973 - Triangle Counting

Post by imnew » Sun Mar 05, 2006 1:20 am

can anyone tell me why am i getting RE? I cant figure it out :(

Code: Select all

#include <cstdio>
#include <vector>

#define MAX 3002

using namespace std;

int f1[MAX], f2[MAX];

int e[MAX][2];

vector<int> a[MAX];

int main() {
    int i, j, s, t, n, m, test;
    long long count;

    scanf("%d", &test);
    while(test--) {
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; ++i) a[i].clear();
        for(i = 0; i < m; ++i) {
            scanf("%d %d", &e[i][0], &e[i][1]);
            a[e[i][0]].push_back(e[i][1]);
            a[e[i][1]].push_back(e[i][0]);
        }
        memset(f1, 0, sizeof(f1));
        memset(f2, 0, sizeof(f2));
        count = 0;
        for(i = 0; i < m; ++i) {
            s = e[i][0];
            t = e[i][1];
            for(j = 0; j < a[s].size(); ++j) f1[a[s][j]] = i + 1;
            for(j = 0; j < a[t].size(); ++j) {
                f2[a[t][j]] = i + 1;
                if(f1[a[t][j]] == i + 1 && a[t][j] != s && a[t][j] != t) ++count;
            }
        }
        printf("%lld\n", count / 3);
    }
    return 0;
}

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

RTE is...

Post by Psyco » Thu Mar 09, 2006 2:26 pm

RTE is...

1. Small array size

2. Devided zero(ex : 0/0, 1/0, 0/1)

I think you are case 2.

Check!

imnew
New poster
Posts: 5
Joined: Sun Feb 12, 2006 6:37 am

Post by imnew » Thu Mar 09, 2006 6:34 pm

there is no division operation (except by a constant: 3) in my code (i think)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Mar 09, 2006 6:51 pm

You're using too much memory (and your solution is too slow and will time out anyway).
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

imnew
New poster
Posts: 5
Joined: Sun Feb 12, 2006 6:37 am

Post by imnew » Thu Mar 09, 2006 8:13 pm

yes, that is true.....
but i want to find the reason for run time error............
anyway, thanks..........

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Mar 09, 2006 8:20 pm

As I said - you use too much memory. When std::vector fails to add a new element due to memory limit, it throws bad_alloc exception which results in RTE.

There might be some other reasons why your code fails, but this is the most important one.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

Re: 10973 - Triangle Counting

Post by shiplu_1320 » Thu Jan 08, 2009 12:37 pm

i'm getting WA!!! :oops: need some critical test cases........

Code: Select all

#include<stdio.h>
#include<math.h>
#include<ctype.h>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<sstream>
#include<iostream>
using namespace std;
#define VI vector<int>
#define VS vector<string>
#define SZ size()
#define PB push_back
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,a,b) for(i=(a);i<(b);i++)
#define FORr(i,a,b) for(i=(a);i>=(b);i--)
#define REPr(i,n) FORr(i,n-1,0)
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define PI 2*acos(0.0)
#define EPS 1e-8

bool G[3005][3005],vi[3005];
int n,tri;
void dfs(int u,int pre)
{
	int v;
	REP(v,n)
	{
		if(u==v)
			continue;
		if(G[u][v])
		{
			if(!vi[v])
			{
				vi[v]=true;
				
				dfs(v,u);
			}
			else if(v!=pre && G[v][pre])
				tri++;
		}
	}
}
int main()
{
	int t,i,x,y,m;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);
		memset(G,0,sizeof(G));
		memset(vi,0,sizeof(vi));
		REP(i,m)
		{
			scanf("%d %d",&x,&y);
			x--;y--;
			G[x][y]=G[y][x]=true;
		}
		tri=0;
		REP(i,n)
		{
			if(!vi[i])
			{
				vi[i]=true;
				dfs(i,-1);
			}
		}
		printf("%d\n",tri);
	}
	return 0;
}
A learner......

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10973 - Triangle Counting

Post by vahid sanei » Sat Jan 24, 2009 2:32 pm

Code: Select all

Accepted
Impossible says I`m possible

Post Reply

Return to “Volume 109 (10900-10999)”