Pagini recente » Cod sursa (job #886585) | Cod sursa (job #1215957) | Cod sursa (job #1067591) | Cod sursa (job #633964) | Cod sursa (job #2012217)
#include <fstream>
#include <vector>
#include <queue>
#define in "ctc.in"
#define out "ctc.out"
#define N 100003
using namespace std;
ifstream fin(in);
ofstream fout(out);
vector<int> g[N],gt[N]; // gt - graf transpus
queue<int> coada[N];
bool f[N],ft[N],fa[N];
int n,m,x,y;
int nctc;
inline void DFS(int nod)
{
vector<int>::iterator it;
f[nod] = 1;
for(it = g[nod].begin(); it != g[nod].end(); ++it)
if(!f[*it])
DFS(*it);
}
inline void DFSt(int nod)
{
vector<int>::iterator it;
ft[nod] = 1;
for(it = gt[nod].begin(); it != gt[nod].end(); ++it)
if(!ft[*it])
DFSt(*it);
}
int main()
{
fin>>n>>m;
while(m--)
{
fin>>x>>y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i=1; i<=n; ++i)
if(!fa[i])
{
DFS(i);
DFSt(i);
++nctc;
for(int i=1; i<=n; ++i)
if(f[i] == ft[i] && f[i] == 1)
{
coada[nctc].push(i);
fa[i] = 1;
}
for(int i=1; i<=n; ++i)
f[i] = ft[i] = 0;
}
fout<<nctc<<"\n";
for(int i=1; i<=nctc; ++i)
{
while(coada[i].empty() == 0)
{
fout<<coada[i].front()<<" ";
coada[i].pop();
}
fout<<"\n";
}
fin.close(); fout.close();
return 0;
}