Pagini recente » Cod sursa (job #3186126) | Cod sursa (job #1768474) | Cod sursa (job #1590316) | Cod sursa (job #2937466) | Cod sursa (job #2565254)
#include <fstream>
#include <vector>
#define NMAX 100000
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector< int > adj[NMAX];
vector< int > stiva;
vector< int > scc[NMAX];
int nrc,disc[NMAX],low[NMAX],cc[NMAX],time;
void dfs(int n1)
{
disc[n1]=low[n1]=++time;
stiva.push_back(n1);
for(vector<int>::iterator it=adj[n1].begin();it!=adj[n1].end();it++)
{
int n2=*it;
if(disc[n2] && !cc[n2])
low[n1]=min(low[n1],disc[n2]);
else if(!disc[n2])
{
dfs(n2);
low[n1]=min(low[n1],low[n2]);
}
}
if(disc[n1]==low[n1])
{
nrc++;
while(stiva.back()!=n1)
{
scc[nrc].push_back(stiva.back());
cc[stiva.back()]=nrc;
stiva.pop_back();
}
scc[nrc].push_back(n1);
cc[n1]=nrc;
stiva.pop_back();
}
}
int main()
{
int n,m,i,j,x,y;
cin>>n>>m;
for(i=1; i<=m; i++)
{
cin>>x>>y;
adj[x].push_back(y);
}
for(i=1; i<=n; i++)
{
if(!disc[i])
{
time=0;
dfs(i);
}
}
cout<<nrc<<'\n';
for(i=1;i<=nrc;i++)
{
for(vector<int>::iterator it=scc[i].begin();it!=scc[i].end();it++)
cout<<*it<<' ';
cout<<'\n';
}
return 0;
}