Pagini recente » Cod sursa (job #65328) | Cod sursa (job #115190) | Cod sursa (job #1918821) | Cod sursa (job #775241) | Cod sursa (job #1669195)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
vector <int> G[100005],/*G1[100005],v,*/rez[100005];
int S[100005],nr;
struct vertex{
int l, id;
bool stack;
}ex{0,0,0};
vector <vertex> marcat;
int k;
stack <int> s;
int index;
/*void dfs1(int nod)
{
marcat[nod]=1;
for(auto p : G1[nod])
if(!marcat[p])
dfs1(p);
v.push_back(nod);
}
void dfs2(int nod,int comp)
{
marcat[nod]=comp;
rez[comp-1].push_back(nod);
for(auto p : G[nod])
if(!marcat[p])
dfs2(p,comp);
}*/
void tarjan(int nod)
{
marcat[nod].id=index;
marcat[nod].l=index;
index++;
//S[++nr]=nod;
s.push(nod);
marcat[nod].stack=true;
for(auto w : G[nod])
if(!marcat[w].id)
tarjan(w), marcat[nod].l=min(marcat[nod].l, marcat[w].l);
else
if(marcat[w].stack)
marcat[nod].l=min(marcat[nod].l, marcat[w].l);
if(marcat[nod].id == marcat[nod].l)
{
int x;
k++;
do{
x=s.top();
s.pop();
marcat[x].stack=0;
rez[k-1].push_back(x);
}while(x!=nod);
}
}
int main()
{
f>>n>>m;
marcat.resize(n+1);
fill(marcat.begin(),marcat.end(),ex);
for(int i=0; i<m; i++)
{
int a,b;
f>>a>>b;
G[a].push_back(b);
//G1[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!marcat[i].id)
tarjan(i);
/*for(int i=1; i<=n; i++)
if(!marcat[i])
dfs1(i);
fill(begin(marcat),end(marcat),0);
int nr=v.size()-1;
for(; nr>=0; nr--)
if(!marcat[v[nr]])
{
dfs2(v[nr],k+1);
k++;
}*/
g<<k<<"\n";
for(int i=0; i<k; i++)
{
for(auto x:rez[i])
g<<x<<" ";
g<<"\n";
}
}