Pagini recente » Cod sursa (job #193280) | Cod sursa (job #84524) | Cod sursa (job #1350171) | Cod sursa (job #1513486) | Cod sursa (job #2346705)
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire();
void afisare();
void BFSp(int nod);
void BFSm(int nod);
int N,M,cnt;
int viz[NMAX];
vector <int> g[NMAX],gt[NMAX],rez[NMAX];
queue <int> q;
int main()
{int i,j;
citire();
for(i=1;i<=N;i++)
if(viz[i]!=-1)
{cnt++;
viz[i]=1;BFSp(i);
viz[i]=-1;
rez[cnt].push_back(i);
BFSm(i);
}
afisare();
return 0;
}
void citire()
{int i,ei,ef;
fin>>N>>M;
for(i=1;i<=M;i++)
{
fin>>ei>>ef;
g[ei].push_back(ef);
gt[ef].push_back(ei);
}
}
void BFSp(int nod)
{
int x;
vector <int>::iterator it;
while(q.size())
q.pop();
q.push(nod);
while(q.size())
{
x=q.front();
q.pop();
for(it=g[x].begin();it!=g[x].end();it++)
if(!viz[*it])
{
viz[*it]=1;
q.push(*it);
}
}
}
void BFSm(int nod)
{
int x;
vector <int>::iterator it;
while(q.size())
q.pop();
q.push(nod);
while(q.size())
{
x=q.front();
q.pop();
for(it=gt[x].begin();it!=gt[x].end();it++)
if(viz[*it]==1)
{
viz[*it]=-1;
q.push(*it);
rez[cnt].push_back(*it);
}
else
if(viz[*it]==0)
{
q.push(*it);
}
}
}
void afisare()
{int i;
fout<<cnt<<'\n';
vector <int>::iterator it;
for(i=1;i<=cnt;i++)
{for(it=rez[i].begin();it!=rez[i].end();it++)
fout<<*it<<' ';
fout<<'\n';
}
}