Pagini recente » Cod sursa (job #1633133) | Cod sursa (job #2826818) | Borderou de evaluare (job #1569260) | Cod sursa (job #2630968) | Cod sursa (job #2534110)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N,M;
int nR;
bool Plus[105],Minus[105],V[105];
vector<int>Ad[105],AdT[105],Comp[105];
void citire()
{
int x,y;
fin>>N>>M;
for(int i=1;i<=M;i++)
{
fin>>x>>y;
Ad[x].push_back(y);
AdT[y].push_back(x);
}
}
void BFS(int nod)
{
queue<int>Q;
int P;
Plus[nod]=1;
Q.push(nod);
while(!Q.empty())
{
P=Q.front();
Q.pop();
for(unsigned i=0;i<Ad[P].size();i++)
if(!Plus[Ad[P][i]])
{
Plus[Ad[P][i]]=1;
Q.push(Ad[P][i]);
}
}
Minus[nod]=1;
Q.push(nod);
while(!Q.empty())
{
P=Q.front();
Q.pop();
for(unsigned i=0;i<AdT[P].size();i++)
if(!Minus[AdT[P][i]])
{
Minus[AdT[P][i]]=1;
Q.push(AdT[P][i]);
}
}
int x=0;
nR++;
for(int i=1;i<=N;i++)
if(i!=nod && Plus[i] && Minus[i])
{
V[i]=1;
Comp[nR].push_back(i);
x++;
}
if(x)
{
Comp[nR].push_back(nod);
V[nR]=1;
}
else
nR--;
}
void rezolvare()
{
for(int i=1;i<=N;i++)
if(!V[i])
{
BFS(i);
memset(Minus,0,sizeof(Minus));
memset(Plus,0,sizeof(Plus));
}
fout<<nR<<'\n';
for(int i=1;i<=nR;i++)
{
sort(Comp[i].begin(),Comp[i].end());
for(unsigned j=0;j<Comp[i].size();j++)
fout<<Comp[i][j]<<" ";
fout<<'\n';
}
}
int main()
{
citire();
rezolvare();
return 0;
}