Pagini recente » Cod sursa (job #712405) | Cod sursa (job #3130678) | Cod sursa (job #124475) | Cod sursa (job #2642121) | Cod sursa (job #2291952)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;
vector<int> G[MAXN];
vector<vector<int>> comps;
int N, M, comps_i=-1, dfs_t=1;
int vis[MAXN], lowlink[MAXN];
bool onstack[MAXN];
stack<int> S;
void Read()
{
ifstream f("ctc.in");
f>>N>>M;
for (int i=1;i<=N;i++)
G[i].push_back(0);
int a, b;
for (int i=0;i<M;i++)
{
f>>a>>b;
G[a].push_back(b);
G[a][0]++;
}
}
void StrongConnect(int a)
{
vis[a]=dfs_t;
lowlink[a]=vis[a];
S.push(a);
onstack[a]=true;
dfs_t++;
for (int i=1;i<=G[a][0];i++)
{
if (vis[G[a][i]]==0) //unvisited
{
StrongConnect(G[a][i]);
lowlink[a]=min(lowlink[a], lowlink[G[a][i]]);
}
else if (onstack[G[a][i]]) //visited before, but a precursor
{
lowlink[a]=min(lowlink[a], vis[G[a][i]]);
}
}
if (lowlink[a]==vis[a])
{
vector<int> tmp;
comps.push_back(tmp);
comps_i++;
while (S.top()!=a)
{
comps[comps_i].push_back(S.top());
S.pop();
}
comps[comps_i].push_back(a);
S.pop();
}
}
void Tarjan()
{
for (int i=1;i<=N;i++)
if (vis[i]==0)
StrongConnect(i);
}
void Write()
{
ofstream g("ctc.out");
g<<comps.size()<<'\n';
for (int i=0;i<comps.size();i++)
{
for (int j=0;j<comps[i].size();j++)
g<<comps[i][j]<<' ';
g<<'\n';
}
}
int main()
{
Read();
Tarjan();
Write();
}