Largest group formed by combinations of pairs - Java

[sharbu]

Sample Input 1:
5 6

2 2
3 3
1 1
2 3
1 4
3 4

first line contains N and C. N is the identity number from 1 to N. C is no of pairs given in following C lines.

based on identity numbers the groups formed are:
2 3 4 1
as 2 is pair with 3 and 3 is pair with 4 and 4 with 1.

Output:
4 \\as it is the largest group formed


Sample input 2:
10 11

1 2
7 8
10 9
10 10
4 4
3 10
8 5
6 5
6 6
9 4
3 2

groups formed:
1 2 3 10 9 4
7 8 5 6
10 9 4

output:
6 //largest group

  import java.util.*;

public class main {    

public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);
    int id=sc.nextInt();
    int no_of_combinations=sc.nextInt();
    int combinations[][]=new int[no_of_combinations][2];
    for(int i=0;i<no_of_combinations;i++)
    {
        combinations[i][0]=sc.nextInt();
        combinations[i][1]=sc.nextInt();
    }
    int maxcount=0;
    int gangs[][]=new int[no_of_combinations][2];
    int x=0,y=0;
    int already_organized=0;
    for(int i=0;i<no_of_combinations;i++)
    {
        already_organized=0;
        for(int j=0;j<x;j++)
        {
            if(gangs[j][0]==combinations[i][0]||gangs[j][0]==combinations[i][1])
            {
                already_organized=1;
                break;
            }
        }
        if(already_organized==0)
        {
            gangs[x][0]=combinations[i][0];
        TreeSet<Integer> members=new TreeSet<Integer>();  
        members.add(gangs[x][0]);
        
        for(int k=0;k<no_of_combinations;k++)
        {
            if((members.contains(combinations[k][0]) && !members.contains(combinations[k][1]))||(members.contains(combinations[k][1]) && !members.contains(combinations[k][0])))
            {
                members.add(combinations[k][0]);
                members.add(combinations[k][1]);
                k=0;
            }
        }
        
        gangs[x][1]=members.size();
        x++;
        }
        
    }
     for(int i=0;i<x;i++)
     {
         if(gangs[i][1]>maxcount)
         {
             maxcount=gangs[i][1];
         }
     }
     System.out.println(maxcount);
    
}

}

My program works fine for normal range inputs but fails for test case inputs which has N and C in the order of 100000 by giving time limit exception.
Is there any better way to crack this question?

[ne555]

explain the problem.
explain your approach.
compute its order.

¿what the hell is `x'?

[Duthomhas]

This problem looks to be finding strongly-connected components in a graph.
I do not understand what your “identity number” is or how it affects your output.
Also, I do not understand how

  10 9 4

is distinct from

  1 2 3 10 9 4

Why not also 9 4 and 3 10 9 4 and 2 3 10 9 4?

[lastchance]

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

void writeGroups( const vector< set<int> > &groups );


int main()
{
   int N, C;
   int i, j;
   vector< set<int> > groups;

   ifstream in( "in.txt" );
   in >> N >> C;

   vector<int> setnum( 1 + N, -1 );    // sentinel -1 means none yet assigned

   while ( C-- )                       // read C lines
   {
      in >> i >> j;

      int si = setnum[i], sj = setnum[j];

      if ( si < 0 && sj < 0 )          // neither yet assigned - create a new set
      {
         set<int> S = { i, j };
         groups.push_back( S );
         setnum[i] = setnum[j] = groups.size() - 1;
      }
      else if ( si < 0 )               // assign i to j's set
      {
         groups[sj].insert( i );
         setnum[i] = sj;
      }
      else if ( sj < 0 )               // assign j to i's set
      {
         groups[si].insert( j );
         setnum[j] = si;
      }
      else if ( si != sj )             // move the smaller set into the larger one
      {                                
         if ( groups[sj].size() < groups[si].size() )
         {
            for ( int k : groups[sj] ) setnum[k] = si;
            groups[si].insert( groups[sj].begin(), groups[sj].end() );
            groups[sj].clear();
         }
         else
         {
            for ( int k : groups[si] ) setnum[k] = sj;
            groups[sj].insert( groups[si].begin(), groups[si].end() );
            groups[si].clear();
         }
      }
   }

   int largest = 0;
   for ( auto S : groups ) if ( S.size() > largest ) largest = S.size();
   cout << largest << '\n';

   // Checks       // COMMENT THE FOLLOWING TWO LINES OUT IF YOU WANT SPEED
   cout << '\n';
   writeGroups( groups );
}



void writeGroups( const vector< set<int> > &groups )
{
   for ( auto S : groups )
   {
      if ( S.size() > 0 )
      {
         for ( int i : S ) cout << i << ' ';
         cout << '\n';
      }
   }
}

in.txt:

10 11
1 2
7 8
10 9
10 10
4 4
3 10
8 5
6 5
6 6
9 4
3 2

Output . The first item is size of largest group; remaining lines are the groups (i.e. connected subgraphs).

6

5 6 7 8 
1 2 3 4 9 10