Pagini recente » Cod sursa (job #2648559) | Cod sursa (job #1021697) | Cod sursa (job #1381642) | Cod sursa (job #1696256) | Cod sursa (job #2352632)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
using namespace std;
const int nmax=100010;
ifstream f("ctc.in");
ofstream g("ctc.out");
list <int> adj[nmax];
list <int> componente[nmax];
int n,m;
int disc[nmax],low[nmax];
int nrcomp,timp;
stack <int> stiva;
bool instiva[nmax];
void dfs(int u)
{
disc[u]=++timp;
low[u]=timp;
stiva.push(u);
instiva[u]=true;
list <int> :: iterator i;
for(i=adj[u].begin();i!=adj[u].end();++i)
{
int v=*i;
if(!disc[v])
{
dfs(v);
low[u]=min(low[v],low[u]);
}
else
if(instiva[v])
low[u]=min(low[u],low[v]);
}
if(disc[u]==low[u])
{
int w;
nrcomp++;
while(stiva.top()!=u)
{
w=stiva.top();
instiva[w]=false;
componente[nrcomp].push_back(w);
stiva.pop();
}
instiva[u]=false;
stiva.pop();
componente[nrcomp].push_back(u);
}
}
void ctc()
{
for(int i=1;i<=n;++i)
if(!disc[i])
dfs(i);
g<<nrcomp<<'\n';
for(int i=1;i<=nrcomp;++i)
{
list <int> :: iterator it;
for(it=componente[i].begin();it!=componente[i].end();++it)
g<<*it<<' ';
g<<'\n';
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;++i)
{
int x,y;
f>>x>>y;
adj[x].push_back(y);
}
ctc();
return 0;
}