10973 - Triangle Counting

[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

[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

Hope this helps,

Yandry.

[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.

[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

[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.)

[Monsoon]

thx a lot

[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.

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

[Psyco]

RTE is...

1. Small array size

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

I think you are case 2.

Check!

[imnew]

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

[Krzysztof Duleba]

You're using too much memory (and your solution is too slow and will time out anyway).

[imnew]

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

[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.

[shiplu_1320]

i'm getting WA!!! 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;
}

[vahid sanei]

Code: Select all

Accepted