Page 2 of 3

Posted: Thu Jan 19, 2006 9:20 pm
by Monsoon
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

Posted: Tue Jan 24, 2006 7:01 am
by neno_uci
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.

Posted: Tue Jan 24, 2006 12:15 pm
by sluga
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.

Posted: Tue Jan 24, 2006 12:41 pm
by Monsoon
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

Posted: Tue Jan 24, 2006 4:53 pm
by mf
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.)

Posted: Tue Jan 24, 2006 5:05 pm
by Monsoon
thx a lot :D

Posted: Wed Jan 25, 2006 12:03 am
by neno_uci
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:

10973 - Triangle Counting

Posted: Sun Mar 05, 2006 1:20 am
by imnew
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;
}

RTE is...

Posted: Thu Mar 09, 2006 2:26 pm
by Psyco
RTE is...

1. Small array size

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

I think you are case 2.

Check!

Posted: Thu Mar 09, 2006 6:34 pm
by imnew
there is no division operation (except by a constant: 3) in my code (i think)

Posted: Thu Mar 09, 2006 6:51 pm
by Krzysztof Duleba
You're using too much memory (and your solution is too slow and will time out anyway).

Posted: Thu Mar 09, 2006 8:13 pm
by imnew
yes, that is true.....
but i want to find the reason for run time error............
anyway, thanks..........

Posted: Thu Mar 09, 2006 8:20 pm
by Krzysztof Duleba
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.

Re: 10973 - Triangle Counting

Posted: Thu Jan 08, 2009 12:37 pm
by shiplu_1320
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;
}

Re: 10973 - Triangle Counting

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

Code: Select all

Accepted