Pagini recente » Cod sursa (job #973207) | Cod sursa (job #696008) | Cod sursa (job #443642) | Cod sursa (job #2978433) | Cod sursa (job #1930273)
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,st[nmax],vf,vf2;
bool viz1[nmax],viz2[nmax];
vector<int> g[nmax],gt[nmax],scc[nmax];
void read()
{
int x,y;
fin >> n >> m;
for(int i = 1;i <= m;i++)
{
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
}
void dfs1(int k)
{
viz1[k] = 1;
for(vector<int>::iterator ii = g[k].begin();ii != g[k].end();++ii)
if(!viz1[*ii])
dfs1(*ii);
st[++vf] = k;
}
void dfs2(int k)
{
viz2[k] = 1;
scc[vf2].push_back(k);
for(vector<int>::iterator ii = g[k].begin();ii != g[k].end();++ii)
if(!viz2[*ii])
dfs2(*ii);
}
int main()
{
read();
for(int i = 1;i <= n;i++)
if(!viz1[i])
dfs1(i);
for(int i = 1;i <= vf;i++)
if(!viz2[st[i]])
{
dfs2(st[i]);
vf2++;
}
fout << vf2 << "\n";
for(int i = 0;i < vf2;i++)
{
for(vector<int>::iterator ii = scc[i].begin();ii != scc[i].end();++ii)
{
fout << *ii << " ";
}
fout << "\n";
}
return 0;
}