Pagini recente » Cod sursa (job #1988943) | Cod sursa (job #2508637) | Cod sursa (job #2944663) | Cod sursa (job #2511329) | Cod sursa (job #1376597)
#include <iostream>
#include <fstream>
#include <vector>
#define plus 1
#define minus -1
#define plusminus 2
using namespace std;
const int nmax=100001;
int N,M,stare[nmax],k;
vector<int> nod_plus[nmax];
vector<int> nod_minus[nmax];
vector<int> conexe[nmax];
void pozitiv_DFS(int sursa)
{
stare[sursa]=plus;
for(int i=0;i<nod_plus[sursa].size();++i)
{
if(stare[nod_plus[sursa][i]]!=plus && stare[nod_plus[sursa][i]]!=3)
pozitiv_DFS(nod_plus[sursa][i]);
}
}
void negativ_DFS(int sursa)
{
if(stare[sursa]==plus)
stare[sursa]=plusminus;
else
stare[sursa]=minus;
for(int i=0;i<nod_minus[sursa].size();++i)
if(stare[nod_minus[sursa][i]]==plus)
negativ_DFS(nod_minus[sursa][i]);
}
void search(int sursa)
{
pozitiv_DFS(sursa);
negativ_DFS(sursa);
int ok=1;
for(int i=1;i<=N;++i)
{
if(stare[i]==plusminus && ok==1)
{
conexe[++k].push_back(i);
ok=0;
}
else if(stare[i]==plusminus)
conexe[k].push_back(i);
if(stare[i]!=plusminus)
stare[i]=0;
else stare[i]=3;
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin>>N>>M;
int sursa,vecin;
for(int i=1;i<=M;++i)
{
fin>>sursa>>vecin;
nod_plus[sursa].push_back(vecin);
nod_minus[vecin].push_back(sursa);
}
for(int i=1;i<=N;++i)
if(stare[i]!=3)
search(i);
fout<<k<<"\n";
for(int i=1;i<=k;++i)
{
for(int j=0;j<conexe[i].size();++j)
fout<<conexe[i][j]<<" ";
fout<<"\n";
}
return 0;
}