Pagini recente » Cod sursa (job #1598863) | Cod sursa (job #1699619) | Cod sursa (job #1665428) | Cod sursa (job #266638) | Cod sursa (job #1876445)
#include <bits/stdc++.h>
using namespace std;
vector <set <int> >gr;
vector <set <int> >gr2;
vector <set <int> >gr3;
int viz[100001], nr;
vector <int> postordine;
ofstream g("ctc.out");
void DFS (int x)
{
viz[x]=1;
set <int> ::iterator it;
for (it=gr[x-1].begin();it!=gr[x-1].end();++it)
if (!viz[*it])
DFS(*it);
postordine.push_back(x);
}
void DFST(int x,int y)
{
viz[x]=0; gr3[y].insert(x);
set<int>::iterator it;
for (it=gr2[x-1].begin();it!=gr2[x-1].end();++it)
if (viz[*it])
DFST(*it,y);
}
int main()
{
set<int>::iterator it;
int i, n, a, b, m;
ifstream f("ctc.in");
f >> n >> m;
int nr=0;
gr2.resize(n);
gr.resize(n);
for (i=1;i<=m;++i)
{
f >> a >> b;
gr[a-1].insert(b);
gr2[b-1].insert(a);
}
set<int> q;
for (i=1;i<=n;++i)
if (!viz[i]) DFS(i);
vector <int>::reverse_iterator it5;
for (it5=postordine.rbegin();it5!=postordine.rend();++it5)
{ if (viz[*it5])
{gr3.push_back(q);
DFST(*it5,nr);
nr++;
}
}
g << nr << "\n";
for (i=0;i<nr;++i)
{
for (it=gr3[i].begin();it!=gr3[i].end();++it)
g << *it << " ";
g << "\n";
}
return 0;
}