Cod sursa(job #1221217)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 19 august 2014 21:35:52
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
 vector <int> v[100005],vt[100005],sol[100005];
 queue <int> q;
 int n,m,use[100005],ok[100005],was[100005],nrc;
int main()
{ int i,j,x,y;
   f>>n>>m;

   for(i=1;i<=m;i++)
    { f>>x>>y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }

    for(i=1;i<=n;i++)
    if (!use[i])
     { use[i]=1;
       memset(ok,0,sizeof(ok));

        memset(was,0,sizeof(was));
        q.push(i); was[i]=1;
         while(!q.empty())
          { x=q.front(); q.pop();
             for(j=0;j<v[x].size();j++)
              if (!use[v[x][j]] && !was[v[x][j]])
               { ok[v[x][j]]++;
                 was[v[x][j]]=1;
                 q.push(v[x][j]);
               }
          }

        memset(was,0,sizeof(was));
        q.push(i); was[i]=1;
         while(!q.empty())
          { x=q.front(); q.pop();
             for(j=0;j<vt[x].size();j++)
              if (!use[vt[x][j]] && !was[vt[x][j]])
               { ok[vt[x][j]]++;
                 was[vt[x][j]]=1;
                 q.push(vt[x][j]);
               }
          }

          nrc++; sol[nrc].push_back(i);
        for(j=1;j<=n;j++)
         if (!use[j] && ok[j]==2)
          { use[j]=1; sol[nrc].push_back(j); }

     }
       g<<nrc<<"\n";
     for(i=1;i<=nrc;i++)
      {for(j=0;j<sol[i].size();j++)
       g<<sol[i][j]<<" ";
        g<<"\n";
      }
    return 0;
}