Pagini recente » Cod sursa (job #685396) | Cod sursa (job #1131841) | Cod sursa (job #2451197) | Cod sursa (job #3031454) | Cod sursa (job #1040573)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=100005;
int n,m,no;
vector<int> g[MAXN],t[MAXN],sol[MAXN];
stack<int> s;
bool uz[MAXN];
void read()
{
ifstream fin("ctc.in");
fin>>n>>m;
int i,x,y;
for (i=1; i<=m; ++i)
{
fin>>x>>y;
g[x].push_back(y);
t[y].push_back(x);
}
fin.close();
}
void dfsg(int u)
{
s.push(u);
uz[u]=true;
for (vector<int>::iterator v=g[u].begin(); v!=g[u].end(); ++v)
{
if (!uz[*v])
dfsg(*v);
}
}
void dfst(int u)
{
uz[u]=true;
sol[no].push_back(u);
for (vector<int>::iterator v=t[u].begin(); v!=t[u].end(); ++v)
{
if (!uz[*v])
{
dfst(*v);
}
}
}
void solve()
{
int i;
for (i=1; i<=n && s.size()!=n; ++i)
{
if (!uz[i])
dfsg(i);
}
for (i=1; i<=n; uz[i]=0, ++i);
while (!s.empty())
{
if (!uz[s.top()])
{
++no;
dfst(s.top());
}
s.pop();
}
}
void write()
{
ofstream fout("ctc.out");
fout<<no<<'\n';
for (int i=1; i<=no; ++i)
{
for (vector<int>::iterator j=sol[i].begin(); j!=sol[i].end(); ++j)
{
fout<<*j<<' ';
}
fout<<'\n';
}
fout.close();
}
int main()
{
read();
solve();
write();
return 0;
}