http://opc.iarcs.org.in/index.php/problems/TASKFORCE
is the problem I’ve been working on for so many hours. Now that I have gotten it accepted, it only runs in time limit for half test cases. Any advice for faster algo?
#include <iostream>
using namespace std;
int k=0,m=0,n=0,size = 0;
int graph[3001][3001];
int force[3001];
int main()
{
cin>>n>>m>>k;
int t1,t2;
for(int i=0;i<3001;i++)
{
force[i]=1;
for(int j=0;j<3001;j++)
{
graph[i][j]=0;
}
}
for(int i=1;i<=m;i++)
{
cin>>t1>>t2;
graph[t1][t2]=1;
graph[t2][t1]=1;
}
int count = 0;
bool done = false;
while(!done)
{
done = true;
count = 0;
for(int i =1;i<=n;i++)
{
count = 0;
if(force[i]!=-1)
{
for(int j = 1;j<=n;j++)
{
if(graph[i][j]&&force[j]!=-1) //-1 means removed from force
count++;
}
if(count<k)
{
done = false;
force[i]=-1;
}
}
}
}
for(int i=1;i<=n;i++)
{
if(force[i]==1)
{
size+=1;
}
}
if(size>0)
cout<<"YES"<<endl<<size;
else
cout<<"NO";
return 0;
}