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

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

10973 - Triangle Counting

Post by Sanny » Fri Nov 11, 2005 11:56 pm

I couldn't find anything better than O(VE) in this problem. Can anybody explain a better algo please?


Regards
Sanny

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Sat Nov 12, 2005 8:51 am

me neither.

I just calculated by frute force :D with some optimizations. My algo depends on number of vertices. Since there isnt any edge into more than 2 triangles, you know there is no more edges than 3 times number of nodes. In general, it's better an algo O(3n*k) than O(n^2 * k).

arahimi
New poster
Posts: 1
Joined: Sat Nov 12, 2005 10:30 am

Wrong Solution

Post by arahimi » Sat Nov 12, 2005 10:39 am

Your assumption that the number of edges in such a graph is less than 3*V is wrong. Consider a complete bi-partite graph of V vertices with V/2 vertices on each part. This graph does not have any triangles and has V^2/4 edges.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sat Nov 12, 2005 4:13 pm

Has anybody got AC in this problem using STL to keep the edge list or adjacency list?

Regards
Sanny

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Sat Nov 12, 2005 5:18 pm

Your assumption that the number of edges in such a graph is less than 3*V is wrong
I have to accept you are allright. Very nice sample. When i solved this problem, i was thinking what was the worst case for number of triangules :D. Well, at least my algo runs on time. I didn't expect such a case.

Thank you, Arahimi.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Nov 13, 2005 10:28 am

I got Runtime error...... why?
I used bool[3001][3001], is this too big?

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sun Nov 13, 2005 10:35 am

Wei-Ming Chen wrote:I used bool[3001][3001], is this too big?
No, my solution also uses such array. :D

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Nov 13, 2005 10:51 am

This is my code. Is where wrong?
I don't like RTE....

#include <stdio.h>
int main()
{
bool a[3001][3001];
int b,c,d,e,f,g,h;
Last edited by Wei-Ming Chen on Sun Nov 13, 2005 11:12 am, edited 1 time in total.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sun Nov 13, 2005 11:02 am

bool a[3001][3001] is too big for stack memory. Declare this as global and you'll be fine.

Regards
Sanny

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Nov 13, 2005 11:07 am

You are right
I got Ac, thank you

User avatar
h001122
New poster
Posts: 9
Joined: Thu Feb 24, 2005 5:59 am

10973 - Triangle Counting

Post by h001122 » Thu Nov 24, 2005 3:58 pm

Code: Select all

#include <iostream>
#include <cstdio>

using namespace std;

bool adj[3001][3001] = {false};
// Graph will be transformed into adjacently matrix.

void reset(); // Reset after each test case.

int main()
{
int t, n, m, a, b, i, j, k;

cin >> t;

while(t--) {
int triangle = 0; // The number of triangle

scanf("%d %d", &n, &m);
for(i = 1; i <= m; i++) {
scanf("%d %d", &a, &b);
adj[a][b] = true;
adj[b][a] = true;
}

// Count triangle in inputed graph.

for(i = 1; i <= m; i++) {
for(j = i + 1; j <= m; j++) {
for(k = j + 1; k <= m; k++) {
if(i != j && i != k && j != k) {
// Are I, J and K connected?
if(adj[i][j] && adj[j][k] && adj[i][k]) {
triangle++;
}
}
}
}
}

cout << triangle << endl;
}

return 0;
}

void reset()
{
int i, j;

for(i = 1; i <= 3000; i++) {
for(j = 1; j <= 3000; j++) {
adj[i][j] = false;
}
}
}
I got Runtime Error.
I think 'bool adj[3001][3001]' isn't such big that it raises stack overflow.
Hmm... I don't know why 'Runtime Error'. Please help me!
Do you know why you're living?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Nov 24, 2005 4:00 pm

Your for-loops should go up to n, not to m.
Btw, you will get TLE with your method.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sat Dec 31, 2005 1:41 pm

Adrian Kuegel wrote:Your for-loops should go up to n, not to m.
Btw, you will get TLE with your method.
Can someone give some test cases , thanks .
I can't find my error :oops:
studying @ ntu csie

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Sat Dec 31, 2005 2:00 pm

What is your problem? WA or TLE?
the worst case for TLE is a bipartite graph. it has no triangle.
you can write a generator for this kind of input.
Last edited by Moha on Sat Dec 31, 2005 3:31 pm, edited 1 time in total.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sat Dec 31, 2005 2:14 pm

Moha wrote:What is your problem? WA or TLE?
the worst case for TLE is a bipartit graph. it has no triangle.
you can write a generator for this kind of input.
sorry , I got wa , I think my method won't get tle
studying @ ntu csie

Post Reply

Return to “Volume 109 (10900-10999)”