Pagini recente » Cod sursa (job #3258244) | Cod sursa (job #2337069) | Cod sursa (job #2948428) | Cod sursa (job #346489) | Cod sursa (job #1261760)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int MAX_N = 100000, MAX_M = 200000;
int lst1[MAX_N+1], urm1[MAX_M+1], vf1[MAX_M+1];
int lst2[MAX_N+1], urm2[MAX_M+1], vf2[MAX_M+1];
int nr1, nr2;
int nrcomp;
vector<int> comp[MAX_N+1];
int n, m;
void add(int x, int y)
{
nr1++;
urm1[nr1] = lst1[x];
lst1[x] = nr1;
vf1[nr1] = y;
nr2++;
urm2[nr2] = lst2[y];
lst2[y] = nr2;
vf2[nr2] = x;
}
int st[MAX_N+1];
int nre;
bool viz[MAX_N+1];
void dfs1(int x)
{
int p = lst1[x];
viz[x] = true;
while(p != 0)
{
if(!viz[vf1[p]])
dfs1(vf1[p]);
p = urm1[p];
}
st[++nre] = x;
}
void dfs2(int x, int k)
{
int p = lst2[x];
viz[x] = false;
while(p != 0)
{
if(viz[vf2[p]])
{
dfs2(vf2[p], k);
comp[k].push_back(vf2[p]);
}
p = urm2[p];
}
}
int main()
{
in >> n >> m;
int i, x, y;
for(i = 0; i < m; i++)
{
in >> x >> y;
add(x,y);
}
for(i = 1; i <= n; i++)
{
if(!viz[i])
dfs1(i);
}
while(nre != 0){
if(viz[st[nre]])
{
dfs2(st[nre],++nrcomp);
comp[nrcomp].push_back(st[nre]);
}
nre--;
}
out << nrcomp << "\n";
for(i = 1; i <= nrcomp; i++)
{
for(int j = 0; j < comp[i].size(); j++)
{
out << comp[i][j] << " ";
}
out << "\n";
}
return 0;
}